Self-Organizing Multi-Agent Systems

Cornelis Jan van Leeuwen

Self-Organizing Multi-Agent Systems

Proefschrift

ter verkrijging van de graad van doctor

aan de Technische Universiteit Delft,

op gezag van de Rector Magnificus Prof. dr. ir. T.H.J.J. van der Hagen,

voorzitter van het College voor Promoties,

in het openbaar te verdedigen op

maandag 8 februari 2021 om 15:00 uur

door

Cornelis Jan van Leeuwen

Master of Science in Artificial Intelligence, University of Groningen, The Netherlands,

born in Delfzijl, The Netherlands.

Dit proefschrift is goedgekeurd door de

promotor: Prof. dr. K.G. Langendoen

copromotor: Dr. P. Pawełczak

Samenstelling promotiecommissie:

Rector Magnificus, | voorzitter
Prof. dr. K.G. Langendoen, | Technische Universiteit Delft
Dr. P. Pawełczak, | Technische Universiteit Delft
Onafhankelijke leden: |
Prof. dr. ir. D.H.J. Epema, | Technische Universiteit Delft
Dr. M.M. de Weerdt, | Technische Universiteit Delft
Prof. dr. J.L. Hurink, | Universiteit Twente
Dr. R. Zivan, | Ben-Gurion University of the Negev, Israel
Prof. dr. G. Picard, | École de Mines de Saint-Étienne, France
Reserve leden: |
Prof. dr. E. Visser, | Technische Universiteit Delft

Printed by: | Ridderprint, The Netherlands
Cover design: | Elizabeth Busey (Bloomington, IN, USA)
| Emanation. Monoprint Collage. 2019
| https://elizabethbusey.com/a-study-in-blues/

Copyright  2021 by C.J. van Leeuwen

ISBN 978-94-6366-362-5

An electronic version of this dissertation is available at
http://repository.tudelft.nl/.

Those who can imagine anything, can create the impossible.
—Alan Turing

Summary

Self-organizing multi-agent systems are systems, comprised of a group of independent agents, that are able to adapt and improve their collective behavior through local interactions, without external intervention. Self-organizing multi-agent systems depend less on human interaction in order stay operational and perform well under varying conditions. This is becoming more important as the scale of networks grows, and the complexity increases. Human operators will no longer be able to keep up with growing networks, or oversee the behavior that has emerged from many local interactions between the system’s components. There are many applications where self-organization is becoming essential in order to continue to develop, for instance smart grids, autonomous vehicles, and computer and communication networks.

Self-organization is a property that can be hard to control; it is a property of the group, but it is defined by the behavior of the individual. Existing solutions often use ad hoc approaches by adding some additional mechanism that implements some (limited) form of self-organization, allowing it to adapt to changing environment. However, even if a system is suitable for changing its configuration at runtime, there is still the problem of coordinating the adaptations between agents. To solve that, cooperation between agents is required.

This thesis addresses the problem of providing self-organization to multi-agent systems, or improve the existing self-organizing capabilities. In order to do this, a framework for self-organization is proposed to guide and ease the implementation of self-organization, making sure that adaptive deployment is possible. Then, different mechanisms are provided that define how to cooperatively make decisions in a network.

A formalization for this distributed decision-making is called Distributed Constraint Optimization Problems (DCOP). In this formalization every decision variable is controlled by an agent, and agents have to communicate with one another in order to find variable assignments that minimize a set of constraints. A new DCOP-solving algorithm called CoCoA is introduced that differs from existing methods, by not relying on iteratively updating an existing solution. At its core, CoCoA shares information locally, so that agents can make decisions taking into account their effects on neighboring agents. This algorithm is extended in CoCoA_CA, which performs an extra step to avoid simultaneous decisions, this avoids potential conflicts in the outcome. Finally, a hybrid mechanism is proposed which combines the advantages of CoCoA and that of existing iterative algorithms.

CoCoA is evaluated in experiments using synthetic benchmark problems such as graph-coloring and semi-randomized problems. More realistic use cases for self-organization are provided in a greenhouse sensor network and wireless power transfer networks. Despite the generic approach for self-organization, there are problem classes that cannot be solved efficiently using a DCOP-based approach. An example is the power dispatch problem faced in smart grids, where there are constraints that involve all agents. For this problem instance, a custom decision-making algorithm called Local Pricing Receding Horizon is introduced based on a market mechanism, where agents negotiate prices to settle a power program.

Samenvatting

Zelforganiserende multi-agent systemen zijn systemen, gebouwd van een groep van onafhankelijk acterende agenten, welke hun collectieve gedrag kunnen aanpassen en verbeteren door lokaal met elkaar te interacteren, zonder invloed van buitenaf. Dit soort zelforganiserende multi-agent systemen zijn minder afhankelijk van menselijke interventie om operationeel te blijven en goed te blijven presteren onder variërende omstandigheden. Dit is nog belangrijker wanneer de schaal van het netwerk en de complexiteit groter worden. Voor een mens wordt het steeds lastiger om de grootte van het netwerk bij te benen, laat staan het complexe gedrag van lokale interacties tussen de componenten te overzien. Er bestaan reeds vele toepassingen waarbij zelforganisatie een belangrijke rol speelt voor de voortgaande ontwikkeling. Voorbeelden hiervan zijn intelligente elektriciteitsnetwerken, zelfrijdende auto’s en uiteraard computer- en communicatienetwerken.

Zelforganisatie is een eigenschap die niet gemakkelijk te beheersen is; het is een eigenschap van de groep, maar wordt bepaald door het gedrag van de individu. Bestaande oplossingen gebruiken dan ook meestal ad hoc benadering om een gelimiteerde vorm van zelforganisatie te implementeren, waardoor het systeem in zich in zekere mate kan aanpassen aan de veranderende omstandigheden. Echter, ook al is een systeem technisch in staat om zichzelf aan te passen, dan resteert nog steeds het probleem om de aanpassingen te coördineren tussen de verschillende agenten. Om ook dit probleem op te lossen is er samenwerking nodig tussen de agenten.

In dit proefschrift wordt getracht zelforganisatie toe te voegen aan multi-agent systemen, of bestaande vormen van zelforganisatie te verbeteren. Om dit te bewerkstelligen wordt een framework geïntroduceerd wat het implementatieproces begeleid en vergemakkelijkt; hierdoor wordt een adaptief systeem mogelijk. Tevens worden enkele mechanismes voorgesteld om te redeneren over hoe een coöperatieve agent als onderdeel van een netwerk beslissingen zou moeten maken.

Een formele beschrijving van het gedistribueerde beslismodel is het zogenaamde Distributed Constraint Optimization Problem (DCOP). In deze formalisatie wordt elke variabele beheerd door een agent, en agenten moeten met elkaar communiceren om een toewijzing te bepalen waarmee de kosten van set van constraints wordt geminimaliseerd. Een algoritme voor DCOPs wordt geïntroduceerd genaamd CoCoA; het verschilt van bestaande algoritmes door niet iteratief een bestaande oplossing te verbeteren. In plaats daarvan wordt in CoCoA lokaal wat informatie gedeeld waardoor een agent een beslissing kan maken, rekening houdende met de gevolgen daarvan op de agenten in zijn buurt. Het CoCoA algoritme wordt uitgebreid in het CoCoA_CA algoritme, waar een stap wordt toegevoegd om gelijktijdige beslissingen te voorkomen, teneinde een conflicterende situatie te vermijden. Tot slot wordt een hybride mechanisme voorgesteld wat de voordelen van CoCoA en bestaande iteratieve methoden met elkaar weet te combineren.

CoCoA wordt geëvalueerd in kunstmatige experimenten, zoals een graph-coloring probleem, evenals semi-willekeurige problemen. Meer realistische toepassingen van zelforganisatie worden behandeld in een sensornetwerk voor glastuinbouw en draadloze oplaadnetwerken. Ondanks de generieke aanpak van zelforganisatie, zijn er typen problemen die niet efficiënt kunnen worden opgelost middels de DCOP aanpak. Als voorbeeld hiervan wordt het power dispatch probleem beschreven, waarbij een planning moet worden gemaakt een elektriciteitsnetwerk. In dit probleem zijn er constraints tussen alle agenten, waardoor een DCOP niet schaalt. Specifiek voor dit probleem wordt een algoritme voorgesteld genaamd Local Pricing Receding Horizon. Dit algoritme gebruikt lokale prijsstrategieën en een gedecentraliseerd marktmechanisme, waarin agenten met elkaar onderhandelen over een prijs om tot een planning te komen.

1 Introduction

Networks of connected computer systems are becoming more and more present in our world. First, networks were relatively small, and every component of the network was carefully designed, engineered, tested, deployed and maintained (Clark 1988; Sculley et al. 2015). However, networks nowadays are vast complex systems and components are being added, updated and removed continuously. The dynamic nature of today’s networks make it impossible for a human operator to control every aspect of a network, let alone a large network of hundreds, if not thousands, of systems.

There are many examples in the real world where networks consist of countless devices that are impossible to maintain by hand; sensor networks (H. Zhang and Hou 2005), smart grids (Kim et al. 2011), autonomous vehicles, IoT (Internet of Things) (Athreya, DeBruhl, and Tague 2013), cellular networks (Johnson and Maltz 1996), and of course, the mother of all: the Internet. Mostly, nodes in these networks are controlled and maintained by other computer systems, but to a lesser extent, there are also systems that rely on self-organization.

Before we elaborate on self-organization, let us propose a definition, since this term is overloaded and may have different meanings in different contexts.

Definition 1.1 (Self-organization). Self-organization is a property of a system composed of subsystems, that are able to improve their collective behavior, either by emergent behavior, or explicit cooperation.

This definition means that a network system is self-organizing if it has the following characteristics (Di Marzo Serugendo, Gleizes, and Karageorgos 2005):

Dynamic operation. The system is capable of changing its mode of operation when appropriate.

A lack of explicit external control. The system receives no external trigger indicating either when or how to change its behavior.

Decentralized control. There is no central authority, instead the system components interact locally with one another, and either explicitly or implicitly affect each other’s behavior.

Note that the last characteristic does not necessarily mean that all components are peers; instead there might be different roles amongst the nodes that define a hierarchy. This could be compared to a bee colony in which there are workers, drones, a queen and other types of bees, which all have their own roles and tasks.

Self-organization typically yields some highly desirable system properties such as increased robustness and reliability, less effort for (human) maintenance, and hence an overall reduce in costs. A related concept to self-organization is autonomic computing, which describes some of the same desirable properties. Instead of networked systems, this concept focuses on the self-managing capabilities of computer systems in general. By that line of logic, self-organization is to networks what autonomic computing is to computers. The concept was first described by the IBM paper on autonomic computing (Kephart and Chess 2003) where it was stated that:

Autonomic Computing helps to address complexity by using technology to manage technology. […] self-managing autonomic capabilities anticipate IT system requirements and resolve problems with minimal human intervention.

The same paper also provides a blueprint for self-managing systems: the MAPE-K framework as depicted in Figure 1.1. This is a generic framework for adaptive systems, in which different components Monitor the operation of the system at hand, Analyze the behavior and determine if any changes are required, Plan a new configuration and finally Execute the changes needed to come to a new state. These four components all have access to a common Knowledge source, which contains information of the system and how to operate it. The MAPE-K framework for self-adaptivity is often used for systems that have to operate in a dynamic environment, and is frequently referenced by other studies for instance in the domains of IoT (Xu, He, and Li 2014), Wireless Sensor Networks (Arora et al. 2004) and Cyber Physical Systems (Derler, Lee, and Vincentelli 2012).

Figure 1.1: Diagram of the MAPE-K adaptation loop. Figure redrawn from (Kephart and Chess 2003).

In our definition of self-organization, the first method of attaining self-organizing behavior is through emergent behavior. In the field of artificial intelligence, the term emergent behavior refers to (seemingly) complex intelligent behavior of a system comprised of multiple simple subsystems. Often this means that a group of agents behaves in a collective intelligent manner, whereas each individual follows a simple set of rules (Mataric 1993). A well-known example involves a flock of birds where the behavior of the group is very complex, yet if one simulates each bird following three simple rules to (i) avoid collisions, (ii) stay close together and (iii) follow the movement of neighbors, the complex behavior “emerges.”

The second method to attain self-organization is through explicit cooperation between components; this is the approach in multi-agent systems.

Definition 1.2 (Multi-agent Systems). Multi-agent Systems are systems in which multiple independent agents act in some shared environment, and solve problems while interacting with each other.

Multi-agent systems is a field of distributed Artificial Intelligence, which exists at least since the late 1980s (Gasser, Braganza, and Herman 1988; Kraus and Lehmann 1995; Ferber 1999). Here, an agent is defined as a distinct entity, capable of making some decisions, with some interfaces for input and output. This definition includes software-based agents, agents in a simulated environment with a virtual presence, and agents with physical hardware connected (robots). Agents may either compete with each other in order to achieve their own individual goals, or they may cooperate to achieve a common goal. The philosophy behind cooperative multi-agent systems is to divide a large problem into many subproblems, which are subsequently solved by independent agents (Jennings 2000).

In the scope of network systems, it is common that every agent runs on, and controls one node. This means that the terms agents and nodes are used interchangeably when multi-agent systems are used to monitor and control network systems.

A formal method for describing cooperative multi-agent problems and the algorithms to solve these problems, is called Distributed Constraint Optimization Problem (DCOP). DCOPs are a type of distributed optimization problems in which variables are controlled by agents that have to find assignments to minimize a cost function over the complete set of variables (Hirayama and Yokoo 1997). This means that the agents share a common goal, and in order to perform well on the global task, have to pass messages between one another in order to coordinate their value assignments, and thus self-organize. A formal definition will be presented in Section 3.2.

Figure 1.2: An example CSP is the 8-queens problem; here an example solution is shown in which no queen on the chessboard can take one of the others.

DCOP originates from the Constraint Satisfaction Problem (CSP) (Fioretto, Pontelli, and Yeoh 2018). CSP is a class of well-studies problems (Hirayama and Yokoo 1997; Minton et al. 1992), in which variables have to be assigned values from a domain, such that a set of constraints are satisfied. These constraints are logical in that their result is either true or false. A famous example of a CSP is the eight queens problem; in this problem eight queens have to be places on a standard eight by eight squared chess board, such that no two queens are able to take one another. One example of a solution to this problem is shown in Figure 1.2.

Distributed Constraint Satisfaction (DCSP, or in other literature also: DisCSP), is an extension of CSP in which the variables are controlled by different agents (Yokoo et al. 1998). The involved agents have to cooperate in order to find an allocation of their corresponding variables such that all constraints are satisfied. At the same time a generalization of CSP is the Constraint Optimization Problem (COP), in which the constraints are no longer logical, but instead can result in any non-negative real number. Then, the problem is no longer about finding a solution that satisfies all constraints, but instead to minimize the sum of all constraints. Similar to how DCSP is an extension of CSP, DCOP is an extension of COP.

By extending the eight-queens problem from a CSP to the class of DCOPs, would mean that instead of placing eight queens so that not one can take another; the problem would require placing, for example, ten queens in such a way that the fewest number of queens can take another queen. Moreover, for every queen there is a separate instance (agent) deciding where to place its assigned queen. This is just an example problem, but DCOPs are often used to formally describe and solve problems for instance for Wi-Fi channel allocation (Duffy, Bordenave, and Leith 2013), power dispatch and balancing in Smart Grids (Fioretto et al. 2017) or even coordination of mobile (robot) search and rescue teams (Zivan, Glinton, and Sycara 2009; Yedidsion, Zivan, and Farinelli 2014).

There exists an extension of the DCOP framework called Asymmetric DCOP (ADCOP) (Grubshtein et al. 2010; Grinshpoun et al. 2013), in which agents may value a set of constrained assignments differently. What this means is that constraints have different costs for the involved agents. This would allow to describe a relation between two agents in which one agent benefits from a certain assignment, but another agent is greatly hindered. For example, in a group of Wi-Fi routers, the transmission powers can be controlled in order to optimize the respective network throughputs. When one router sets it power to the maximum possible, it will increase the throughput of its own network, but will probably cause interference to neighboring networks. Hence, a more coordinated strategy is required.

In the context of dynamic systems, DCOPs have been applied as superstabilizing (Petcu and Faltings 2005b, 2007) DCOP algorithms, that continuously adapt to changes in the environment. The max-sum algorithm can also run continuously (Farinelli et al. 2008), allowing for a best-effort optimum at any time. This strategy could pertain to changes in constraint costs, but it is unclear how added or removed nodes could be taken into account. Another more formal way of defining dynamic problems, lead to a family of algorithms dealing with Dynamic DCOPs (DDCOPs) (Lass, Sultanik, and Regli 2008; Yeoh et al. 2015; Hoang et al. 2016, 2017). These algorithms proactively take into account potential future changes in the problem, and minimize the expected future costs, considering a model of foreseen future changes.

According to recent research, problems in self-organization in multi-agent systems can be categorized in either one of the following four main categories (Ye, Zhang, and Vasilakos 2016):

Task/Resource allocation (Fatima and Wooldridge 2001; C. Zhang, Lesser, and Shenoy 2009; Kash, Procaccia, and Shah 2014) is the problem where either tasks or resources have to be allocated to a group of agents in order to deal with them as efficiently as possible. Typically, in task allocation an agent cannot finish all tasks by itself (in time) and tasks have to be allocated to different agents to carry out. Moreover, there is often a dependency of tasks from one to another, which has to be taken into consideration when assigning tasks. Allocation of resources is a similar problem, where agent have to share (a set of) scarce resources such that all agents can perform their tasks.

Relation adaptation and coordination (Glinton, Sycara, and Scerri 2008; Griffiths and Luck 2010; Kota, Gibbins, and Jennings 2012), also referred to as relation modification, studies how relations can be adapted in order to achieve efficient cooperation in a multi-agent system. A group of agents has to rearrange their internal structure in order to adapt to dynamic operating conditions and environments. This category includes leader election, group formation, and other problems in which agents change the relations (or type thereof) with other agents.

Coordinated reasoning and learning (Abdallah and Lesser 2008; Elidrisi et al. 2014) is the problem that agents face when they have to learn about the effect of their actions on the environment. Either by trial-and-error, or by an underlying model, agents must decide on how to act in the environment in order to achieve a better state, according to some utility function. In the multi-agent domain, groups of agents can coordinate strategies in order to determine the most effective course of actions, especially when the strategies have to be in line with one another.

Collective decision-making and planning (Boutilier 1996; Yeoh and Yokoo 2012) relates to economics and social sciences, and studies the issue of how to coordinate decisions made by agents. In many contexts of multi-agent systems, the choice of one agent influences the performance of those around it. Hence, decisions have to take into account actions of others, and should be coordinated to achieve the optimal group result. In a multi-agent context this is especially challenging since only local perception and agent-to-agent communication can be taken into account, since no agent has global knowledge. Planning can be considered a special case of decision-making, when a series of sequential choices have to be made.

These issues are overlapping, and in many real applications, solutions from multiple categories have to be applied.

1.1 Problem Statement

Although some existing networks already depend on self-organization to keep up with changing operating conditions, this property is hard to master, and there are often still many places to improve. The goal could be the reliability, efficiency, speed or cost of the system, but also that of the coordination strategy itself. In this thesis the self-organizing behavior in large networked systems is studied, and we formulate the main research question as follows:

How can we achieve self-organization, or improve the self-organization capabilities in a network of cooperative agents?

In order to answer this question, we can divide it into the following two main challenges:

Challenge 1: Create a framework that allows self-organizing systems to redefine their deployment. In some situations the desired behavior of a network cannot entirely be specified a priori to its deployment. Some design decisions must be made when the system is already operational. Delaying these decisions can be used to gain robustness of the system when facing operational changes (internal) or environmental changes (external). Traditionally, changing the system deployment implies that some human intervention is required in order to implement the new configuration. This can be very expensive, slow, tedious and perhaps even dangerous in hostile environments or hard-to-reach areas. Therefore, a self-organization framework is needed that can redefine a system’s deployment at runtime.

Challenge 2: Find or improve strategies to coordinate collective behavior. Changing the operation of a single node in a network is rarely the solution to improve the overall behavior of the complete network. Under most circumstances changes across the network need to be coordinated and orchestrated in an “intelligent” manner. Moreover, a reconfiguration might increase the local performance of a single node, but decrease the global performance of the complete network. Cooperation between nodes is absolutely required in order to achieve top-level goals in the complete network. Therefore, a strategy must be found (or existing strategies improved) to coordinate behavior between nodes.

These two challenges are not independent of one another; both will need to be addressed in order to add self-organizing capabilities to a system. Furthermore, the self-organization process of the system should not be taking too much communication or computation overhead, especially when designing a low-powered embedded systems with limited resources. The problem underlying self-organization is a very challenging one by itself. The multi-agent variable assignment problem can be formulated as a DCOP, which is known to be NP-hard (Modi 2003). For this reason we should not design a system that searches the optimal solution, but we will have to make sure that the strategy used for achieving self-organization is properly balanced in terms of required resources and benefit for the “primary” system.

1.2 Contributions and Thesis Outline

In this thesis the aforementioned challenges will be addressed in the following manner.

Firstly, Challenge 1 is addressed in Chapter 2. We elaborate on the notion of self-organization, and introduce a framework for self-organizing systems. This framework describes a two-layered approach where all self-organization tasks are executed in a “secondary” layer, which runs independent of the primary system. This secondary layer gathers performance indicators and acts on the deployment of the system, optimizing its behavior. The framework will be put to use in a first use case of self-organizing state estimation in a greenhouse climate control system.

Secondly, Challenge 2 is addressed using two different strategies throughout this thesis:

CoCoA, a newly proposed (A)DCOP solver is developed in Chapter 3 (which is subsequently improved in Chapters 4 and 5),

a decentralized market based mechanism called LP-RH is used in Chapter 6.

CoCoA is an algorithm to solve ADCOPs, which coordinates collective behavior. Moreover, it is designed to do so using fewer system resources than comparative algorithms. Through several experiments, the performance of the CoCoA algorithm is compared to state-of-the-art DCOP solvers. Finally, it is shown how CoCoA would solve the same greenhouse problem from Chapter 2.

In Chapter 4 a variant of the CoCoA algorithm is described that is specifically suited to deal with hard constraints. The new variant is applied to the Wireless Power Transfer (WPT) problem (Q. Liu, Yıldırım, et al. 2016). WPT is a technology where power is sent from a set of transmitters to receivers, to allow for remote wireless charging. Safety regulations apply such that electromagnetic radiation never exceeds safe human operation levels. In this particular problem hard constraints are particularly crucial to the safe operation of the network, and hence the extension of the CoCoA algorithm guarantees avoiding violating such hard constraints.

Chapter 5 describes a general extension of DCOP-solving algorithms to allow running of multiple existing algorithms, in order to cooperate and find a better solution together, than either one would on its own. The initialization of a DCOP algorithm turns out to be particularly important, and by using CoCoA for initialization, we see that the eventual solution cost decreases, and requires less time to converge.

Finally, not all types of problems can be cast (efficiently) as a DCOP, hence a different method for addressing Challenge 2 is proposed in Chapter 6. A coordination algorithm called Local Pricing Receding Horizon, is introduced in order to facilitate self-organization of the power dispatch problem in smart grids. This approach uses a more hierarchical approach than a DCOP-based solution, and is more fitting to the topology of the energy distribution network. The proposed solution uses a multi-agent based strategy to solve the problem using a combination of economic steering signals to incentivize the agents and local optimization to find an economic and sustainable power dispatch.

The thesis concludes in Chapter 7, where a brief overview of the contributions and results is provided, as well as an answer to the main research question and the two above-mentioned challenges.

2 Self Organizing State Estimation

2.1 Introduction

Self-organization and self-optimization are approaches to address the practical challenges of large-scale sensor and actuator (control) networks such as easy deployment, robustness and energy efficiency. In this chapter the first challenge of implementing self-organization is addressed: to create a framework that allows a system to redefine its deployment. The framework proposed in this chapter, aims to add self-organizing properties to a multi-agent system; specifically for self-organization of a sensor network. This framework will enable the system to cope with changing system configurations (i.e. adding and removing subsystem components) without re-programming the existing set-up (ease-of-deployment), to support a mobile group of subsystems observing particular areas (dynamic sensor management), to adjust on environmental changes affecting the communication resource (changing network capacities) and to adapt to a variety of system goals during operation depending on current needs and the monitored situation (multi-purpose).

In this chapter we propose a framework for self-organization, and apply it to distributed state estimation. Distributed signal processing components can be interchanged or reconfigured, depending on the requirements and system context. This system was earlier presented in (Sijs and Papp 2012), and is demonstrated in a greenhouse scenario, where the temperature distribution within the greenhouse is to be estimated. The main reason for selecting distributed state estimation is that state estimation is used in a wide variety of applications, such as object tracking, traffic management and indoor climate control, to name a few. Yet, the proposed reconfiguration framework is applicable for any system in which state estimation is the key component for processing sensor measurements, as well for many more multi-agent systems in general. In what follows a generalized framework is presented for reconfigurable state estimating systems.

Notation and Preliminaries Throughout this chapter, the following notation will be used: ℝ\mathbb{R}, ℝ>0\mathbb{R}_{>0}, ℤ\mathbb{Z} and ℤ>0\mathbb{Z}_{>0} define the set of real numbers, non-negative real numbers, integer numbers and non-negative integer numbers, respectively. For any 𝒞⊂ℝ\mathcal{C} \subset \mathbb{R}, let ℤ𝒞:=ℤ∩𝒞\mathbb{Z}_{\mathcal{C}} := \mathbb{Z}\cap \mathcal{C}. The notation 0 is used to denote either zero, the null-vector or the null-matrix of appropriate dimensions, while InI_{n} denotes the n×nn\times n identity matrix. The transpose, inverse and determinant of a matrix A∈ℝn×nA \in \mathbb{R}^{n \times n} are denoted as A⊤A^{\top}, A−1A^{-1} and |A||A|, respectively. Further, A12A^\frac{1}{2} denotes the Cholesky decomposition of a matrix An×nA^{n \times n} (if it exists). Given that a random vector x∈ℝnx \in {\mathbb{R}^{n}} is Gaussian distributed, denoted as x∼G(μ,Σ)x \sim G(\mu,\Sigma), then μ∈ℝn\mu \in \mathbb{R}^{n} and Σ∈ℝn×n\Sigma \in \mathbb{R}^{n \times n} are the mean and covariance of xx.

2.2 Distributed State Estimation

Since this chapter focuses on reconfigurable distributed state estimation, this section starts off by considering a linear process model describing the state dynamics. In this context, several distributed solutions of the Kalman filter have been explored—see for example, solutions proposed in (Durrant-Whyte, Rao, and Hu 1990; Kirti and Scaglione 2008; Ribeiro et al. 2010; Sijs and Lazar 2011) and the references therein. This section aims to derive a general framework, so that most of the currently available distributed Kalman filtering (DKF) solutions can be employed in the proposed reconfiguration scheme. To that extent, let us start with the state estimation problem, after which the generalized framework is introduced along with some illustrative estimation algorithms.

2.2.1 Problem Formulation

Let us consider a linear process that is observed by a sensor network with the following description. The networked system consists of NN sensor nodes, in which a node i∈𝒩i \in \mathcal{N} is identified by a unique number within 𝒩:=ℤ[1,N]\mathcal{N}:= \mathbb{Z}_{[1,N]}. The set 𝒩i⊆𝒩\mathcal{N}_{i} \subseteq \mathcal{N} is defined as the collection of neighboring nodes j∈𝒩j \in \mathcal{N} that exchange data with node ii.

The dynamical process measured by each node i∈𝒩i \in \mathcal{N} is described with discrete-time process model, for some local sampling time τi∈ℝ>0\tau_{i} \in \mathbb{R}_{>0} and some 𝗄\textsf{k}-th sample instant, i.e., x[𝗄i]=Aτix[𝗄i−1]+w[𝗄i−1],yi[𝗄i]=Cix[𝗄i]+vi[𝗄i],\begin{aligned} \label{eq:fusion:process_model} x[\mathsf{k}_{i}] & = A_{\tau_i}x[\mathsf{k}_{i}-1] + w[\mathsf{k}_{i}-1],\\ y_{i}[\mathsf{k}_{i}] & = C_{i}x[\mathsf{k}_{i}] + v_{i}[\mathsf{k}_{i}],\end{aligned} where the state and local measurement are denoted as x∈ℝnx \in \mathbb{R}^{n} and yi∈ℝmiy_{i} \in \mathbb{R}^{m_{i}}, respectively. Here, nn and mim_{i} correspond to the number of elements in the state and the measurements of ii, respectively. The process noise w∈ℝnw \in \mathbb{R}^{n} and measurement noise vi∈ℝmiv_{i} \in \mathbb{R}^{m_{i}} follow the Gaussian distributions w[𝗄i]∼G(0,Qτi)w[\mathsf{k}_{i}] \sim G(0,Q_{\tau_i}) and vi[𝗄i]∼G(0,Vi)v_{i}[\mathsf{k}_{i}] \sim G(0,V_{i}), for some Qτi∈ℝn×nQ_{\tau_i} \in \mathbb{R}^{n \times n} and Vi∈ℝmi×miV_{i} \in \mathbb{R}^{m_{i} \times m_{i}}. AτiA_{\tau_i} and QτiQ_{\tau_i} are the variance parameters of the physical process model. Similarly, CiC_i and ViV_i are parameters of the sensor model of node ii, defining how a measurement is obtained from the actual state. A method to compute the model parameters AτiA_{\tau_i} and QτiQ_{\tau_{i}} from a corresponding continuous-time process model ẋ=Fx+w\dot{x}=Fx+w with model parameter FF, yields Aτi:=eFτiandQτi:=Bτicov(w(t−τi))Bτi⊤,withBτi:=∫0τieFηdη.\begin{aligned} \label{eq:fusion:timemodel} &A_{\tau_{i}} := e^{F \tau_{i}} \quad \text{and} \quad Q_{\tau_{i}} := B_{\tau_{i}} \text{cov}\left(w(t-\tau_{i})\right)B_{\tau_{i}}^{\top},\\ &\text{with} \quad B_{\tau_{i}} := \int_{0}^{\tau_{i}} e^{F \eta}d\eta.\end{aligned}

In distributed state estimation, the goal of a sensor network is to compute a local estimate xi∈ℝnx_{i} \in \mathbb{R}^{n} of the global state xx in each node ii. Since the process model is linear and both noises are Gaussian distributed, it is appropriate to assume that the random variable xi[𝗄]x_{i}[\mathsf{k}] is Gaussian distributed as well, i.e., xi[𝗄i]∼G(x̂i[𝗄i],Pi[𝗄i])x_{i}[\mathsf{k}_{i}] \sim G(\hat{x}_{i}[\mathsf{k}_{i}],P_{i}[\mathsf{k}_{i}]) for some mean x̂i[𝗄i]∈ℝn\hat{x}_{i}[\mathsf{k}_{i}] \in \mathbb{R}^{n} and error covariance Pi[𝗄i]∈ℝn×nP_{i}[\mathsf{k}_{i}] \in \mathbb{R}^{n \times n}. To that extent, each node ii performs a local estimation algorithm for computing xix_{i} based on its local measurement yiy_{i} and on the data shared by its neighboring nodes j∈𝒩ij \in \mathcal{N}_{i}.

Existing methods on DKF present solutions for computing xix_{i} and determine what variables should be exchanged, at what time and with which nodes, e.g. (Durrant-Whyte, Rao, and Hu 1990; Kirti and Scaglione 2008; Ribeiro et al. 2010; Sijs and Lazar 2011). The goal of the reconfiguration framework is to reason about the design decisions made by these existing solutions and to select the most appropriate one for the current situation (depending on available communication and computational resources and on the estimation performance). This reasoning process will be addressed in a “management layer” encapsulating the variants for local Kalman filtering, which will be discussed in Section 2.3.3.

Figure 2.1: A network of Kalman filters supported by a management layer.

In order to be able to reason about different configurations, the alternatives for state estimation solutions should be described within a generalized framework, otherwise it is infeasible to compare the different alternatives objectively. Let us introduce such a general framework for distributed state estimation.

2.2.2 A General Framework for Distributed Kalman Filtering

The functional framework for computing the local estimate xix_{i} is derived from existing DKF solutions. Typically, these solutions propose that each node ii performs a Kalman filter (locally) based on its local measurement yiy_{i} and thereby, establishes an initial estimate xi∼G(x̂i,Pi)x_{i} \sim G(\hat{x}_{i},P_{i}), e.g., in (Durrant-Whyte, Rao, and Hu 1990; Kirti and Scaglione 2008; Ribeiro et al. 2010; Sijs and Lazar 2011) and some overview articles in (Carli et al. 2008; Sijs 2012). After that, different DKF solutions propose different types of variables exchanged between two neighboring nodes ii and jj, being:

Local measurements: node ii receives yjy_{j} for all j∈𝒩ij \in \mathcal{N}_{i}, which can be exploited for updating xix_{i} via a Kalman filter.

Local estimates: node ii receives xj∼G(x̂j,Pj)x_{j} \sim G(\hat{x}_{j},P_{j}) for all j∈𝒩ij \in \mathcal{N}_{i}, which can be exploited for updating xix_{i} via various merging solutions, e.g. consensus or state fusion.

Based on the currently available DKF methods a generalized local estimation function is designed relying on the node’s local measurement and on data received from neighboring nodes. The corresponding framework consisting of so called “functional primitives” is depicted in Figure 2.2. Each functional primitive of this framework, i.e., the Kalman filtering function fKFf_{\text{KF}} and the merging function fMEf_{\text{ME}}, is characterized by a specific algorithm, though it is not necessary to specify them prior to deployment. Instead, nodes are deployed with a number of suitable implementations for each functional primitive, from which a selection can be made during operation. Alternative implementations related to computing local estimation results of a single node xi∼G(x̂i,Pi)x_{i} \sim G(\hat{x}_{i},P_{i}) and that of multiple nodes xi+∼G(x̂i+,Pi+)x_{i^+} \sim G(\hat{x}_{i^+},P_{i^+}) are presented, next. Note that the subscript i+i+ indicates that the estimate or error covariance is based on a set of nodes including ii and at least one other node.

Figure 2.2: A framework of the generalized local estimation function, which consists of functional primitives, performed by each node ii in the network, supported by measurements of another node jj The inputs of the functions differ slightly per implemented function.

Remark 2.1. Note that the measurement model yj[𝗄i]=Cjx[𝗄i]+vj[𝗄i]y_{j}[\mathsf{k}_{i}] = C_{j}x[\mathsf{k}_{i}] + v_{j}[\mathsf{k}_{i}] should be available to node ii before yj[𝗄i]y_{j}[\mathsf{k}_{i}] can be exploited. Therefore, node jj shares the local measurement (yj,Cj,Vj)(y_{j},C_{j},V_{j}), while if node jj shares local estimates, it exchanges (x̂j,Pj)(\hat{x}_{j},P_{j}). This implies that the received data of Figure 2.2, yields:

𝕐j⊂ℝmj,ℝmj×n,ℝmj×mj\mathbb{Y}_{j}\subset \mathbb{R}^{m_{j}}, \mathbb{R}^{m_{j} \times n}, \mathbb{R}^{m_{j} \times m_{j}} is the collection of (yj,Cj,Vj)(y_{j},C_{j},V_{j}) received from neighboring nodes j∈𝒩ij \in \mathcal{N}_{i}. Note that 𝕐j\mathbb{Y}_{j} could be empty, for example, when none of the nodes j∈𝒩ij \in \mathcal{N}_{i} shares its local measurement;

𝕏j⊂ℝn,ℝn×n\mathbb{X}_{j}\subset \mathbb{R}^{n}, \mathbb{R}^{n \times n} is the collection of (x̂j,Pj)(\hat{x}_{j},P_{j}) received from neighboring nodes j∈𝒩ij \in \mathcal{N}_{i}. Similar as to 𝕐j\mathbb{Y}_{j}, also 𝕏j\mathbb{X}_{j} can be an empty collection.

Let us continue with a detailed description of the Kalman filtering function in Figure 2.2. This functional primitive combines the local yi[𝗄i]y_{i}[\mathsf{k}_{i}] with the received measurements yj[𝗄i]y_{j}[\mathsf{k}_{i}] to update its cooperative local estimate xi+[𝗄i−1]∼G(x̂i+[𝗄i−1],Pi+[𝗄i−1])x_{i^{+}}[\mathsf{k}_{i}-1] \sim G(\hat{x}_{i^{+}}[\mathsf{k}_{i}-1],P_{i^{+}}[\mathsf{k}_{i}-1]). Measurements are combined via the original Kalman filter or by the alternative Information filter, which was proposed in (Durrant-Whyte, Rao, and Hu 1990). For this latter approach, measurements are rewritten into their information form, for some zj∈ℝnz_{j} \in \mathbb{R}^{n} and Zj∈ℝn×nZ_{j} \in \mathbb{R}^{n \times n}, i.e., zj[𝗄i]:=Cj⊤Vj−1yj[𝗄i]andZj[𝗄i]:=Cj⊤Vj−1Cj.z_{j}[\mathsf{k}_{i}] := C_{j}^{\top}V_{j}^{-1}y_{j}[\mathsf{k}_{i}] \quad \text{and} \quad Z_{j}[\mathsf{k}_{i}] := C_{j}^{\top}V_{j}^{-1}C_{j}.

The Information filter has similar results as the original Kalman filter but differs in computational demand. Furthermore, the information filter is more convenient when the amount of received measurements (yj,Cj,Vj)∈𝕐j(y_{j},C_{j},V_{j}) \in \mathbb{Y}_{j} varies at sample instants. Therefore, the Kalman filtering function in the framework of Figure 2.2 employs the Information filter. More precisely, fKF(⋅,⋅,⋅)f_{\text{KF}}(\cdot,\cdot,\cdot) is a function with three inputs and two outputs according to the following characterization:

(x̂i[𝗄i],Pi[𝗄i]):=fKF(x̂i+[𝗄i−1],Pi+[𝗄i−1],𝕐j[𝗄i])(\hat{x}_{i}[\mathsf{k}_{i}],P_{i}[\mathsf{k}_{i}]) := f_{\text{KF}}(\hat{x}_{i^{+}}[\mathsf{k}_{i}-1],P_{i^{+}}[\mathsf{k}_{i}-1],\mathbb{Y}_{j}[\mathsf{k}_{i}]) Pi[𝗄i]=(Mi−1+Zi[𝗄i]+∑(yj,Cj,Vj)∈𝕐j[𝗄i]Zj[𝗄i])−1,x̂i[𝗄i]=Pi[𝗄i](Mi−1Aτix̂i+[𝗄i−1]+zi[𝗄i]+∑(yj,Cj,Vj)∈𝕐j[𝗄i]zj[𝗄i]),Mi=AτiPi+[𝗄i−1]Aτi⊤+Qτi.\begin{aligned} P_{i}[\mathsf{k}_{i}] &= \Big(M_{i}^{-1} + Z_{i}[\mathsf{k}_{i}] + \sum_{(y_{j},C_{j},V_{j}) \in \mathbb{Y}_{j}[\mathsf{k}_{i}]} Z_{j}[\mathsf{k}_{i}]\Big)^{-1},\\ \hat{x}_{i}[\mathsf{k}_{i}] &= P_{i}[\mathsf{k}_{i}]\Big(M_{i}^{-1} A_{\tau_{i}}\hat{x}_{i^{+}}[\mathsf{k}_{i}- 1] + z_{i}[\mathsf{k}_{i}] + \sum_{(y_{j},C_{j},V_{j}) \in \mathbb{Y}_{j}[\mathsf{k}_{i}]} z_{j}[\mathsf{k}_{i}]\Big),\\ M_{i} &= A_{\tau_{i}}P_{i^{+}}[\mathsf{k}_{i}-1]A_{\tau_{i}}^{\top} + Q_{\tau_{i}}.\end{aligned}

The merging function of Figure 2.2, introduced as fME(⋅,⋅,⋅)f_{\text{ME}}(\cdot,\cdot,\cdot), merges the local estimate xi[𝗄i]x_{i}[\mathsf{k}_{i}] with the received estimation variables xj∼(x̂j,Pj)∈𝕏j[𝗄i]x_{j} \sim (\hat{x}_{j},P_{j}) \in \mathbb{X}_{j}[\mathsf{k}_{i}] into a new estimate xi+[𝗄i]∼G(x̂i+[𝗄i],Pi+[𝗄i])x_{i^{+}}[\mathsf{k}_{i}] \sim G(\hat{x}_{i^{+}}[\mathsf{k}_{i}],P_{i^{+}}[\mathsf{k}_{i}]). Typically, the functional primitive fME(⋅,⋅,⋅)f_{\text{ME}}(\cdot,\cdot,\cdot) is based on solutions for merging two state estimation results xix_{i} and xjx_{j}, yielding a recursive behavior to merge all received estimation results. This means that the merging function fME(⋅,⋅,⋅)f_{\text{ME}}(\cdot,\cdot,\cdot) performed by a node ii has the following definition:

(x̂i+[𝗄i],Pi+[𝗄i]):=fME(x̂i[𝗄i],Pi[𝗄i],𝕏j[𝗄i])(\hat{x}_{i^{+}}[\mathsf{k}_{i}],P_{i^{+}}[\mathsf{k}_{i}]) := f_{\text{ME}}\left(\hat{x}_{i}[\mathsf{k}_{i}],P_{i}[\mathsf{k}_{i}],\mathbb{X}_{j}[\mathsf{k}_{i}]\right) for each estimate (x̂j[𝗄i],Pj[𝗄i])∈𝕏[𝗄i] do (x̂i[𝗄i],Pi[𝗄i])=Ω(x̂i[𝗄i],Pi[𝗄i],x̂j[𝗄i],Pj𝗄i]),endx̂i+[𝗄i]=x̂i[𝗄i],Pi+[𝗄i]=Pi[𝗄i],\begin{aligned} &\text{for each estimate $(\hat{x}_{j}[\mathsf{k}_{i}],P_{j}[\mathsf{k}_{i}]) \in \mathbb{X}[\mathsf{k}_{i}]$ do }\\ &\quad (\hat{x}_{i}[\mathsf{k}_{i}],P_{i}[\mathsf{k}_{i}]) = \Omega\left(\hat{x}_{i}[\mathsf{k}_{i}], P_{i}[\mathsf{k}_{i}], \hat{x}_{j}[\mathsf{k}_{i}], P_{j} \mathsf{k}_{i}]\right),\\ &\text{end}\\ &\hat{x}_{i^{+}}[\mathsf{k}_{i}] = \hat{x}_{i}[\mathsf{k}_{i}],\quad P_{i^{+}}[\mathsf{k}_{i}] = P_{i}[\mathsf{k}_{i}],\end{aligned}

Ω(⋅,⋅,⋅,⋅)\Omega(\cdot,\cdot,\cdot,\cdot) is the inner merging function for merging the local estimation results xix_{i} with received estimation results xjx_{j}. Let us present three examples from the literature of such inner merging functions Ω(⋅,⋅,⋅,⋅)\Omega(\cdot,\cdot,\cdot,\cdot) one synchronization and two fusion approaches.

2.2.2.1 Synchronization Merging

Recent DKF solutions, e.g., (Kirti and Scaglione 2008; Ribeiro et al. 2010), adopt a synchronization approach to characterize fME(⋅,⋅,⋅)f_{\text{ME}}(\cdot,\cdot,\cdot). Such an approach stems from the idea of synchronizing different internal clocks in the network. Typically, synchronization is employed on the estimated means, for some scalar weight ωij∈ℝ>0\omega_{ij} \in \mathbb{R}_{>0}, yielding the following inner-merging function:

SY: (x̂i[𝗄i],Pi[𝗄i])=Ω(x̂i[𝗄i],Pi[𝗄i],x̂j[𝗄i],Pj[𝗄i])(\hat{x}_{i}[\mathsf{k}_{i}],P_{i}[\mathsf{k}_{i}]) = \Omega\left(\hat{x}_{i}[\mathsf{k}_{i}], P_{i}[\mathsf{k}_{i}], \hat{x}_{j}[\mathsf{k}_{i}], P_{j}[\mathsf{k}_{i}]\right) x̂i[𝗄i]=(1−ωij)x̂i[𝗄i]+ωijx̂j−1[𝗄i],Pi[𝗄i]=Pi[𝗄i].\begin{aligned} \hat{x}_{i}[\mathsf{k}_{i}] &= (1-\omega_{ij})\hat{x}_{i}[\mathsf{k}_{i}] + \omega_{ij}\hat{x}_{j}^{-1}[\mathsf{k}_{i}],\\ P_{i}[\mathsf{k}_{i}] &= P_{i}[\mathsf{k}_{i}].\end{aligned}

for establishing the weights ωij\omega_{ij} have been presented in literature extensively, for example in  (Xiao and Boyd 2004; Tahbaz-Salehi and Jadbabaie 2010).

Merging solutions that take the combination of error covariances into account in addition to a combined estimated mean are known as fusion solutions. An optimal fusion method was presented in (Bar-Shalom and Campo 1986), though it requires that correlation of the two prior estimates is available. In the considered sensor networks one cannot impose such a requirement, as it amounts to keeping track of shared data across the entire network. Alternative fusion methods that can cope with an unknown correlation are covariance intersection (CI) and ellipsoidal intersection (EI), as proposed in (Julier and Uhlmann 1997) and (Sijs and Lazar 2012), respectively. We will discuss these solutions below.

2.2.2.2 Covariance Intersection

In CI the fusion function is characterized as a convex combination of the two prior estimates xix_{i} and xjx_{j}, for some scalar weight defined as ωij=tr(Pi)(tr(Pi)+tr(Pj))−1\omega_{ij} = \text{tr}(P_{i})\left(\text{tr}(P_{i}) + \text{tr}(P_{j})\right)^{-1}, i.e.,

CI: (x̂i[𝗄i],Pi[𝗄i])=Ω(x̂i[𝗄i],Pi[𝗄i],x̂j[𝗄i],Pj[𝗄i])(\hat{x}_{i}[\mathsf{k}_{i}],P_{i}[\mathsf{k}_{i}]) = \Omega\left(\hat{x}_{i}[\mathsf{k}_{i}], P_{i}[\mathsf{k}_{i}], \hat{x}_{j}[\mathsf{k}_{i}], P_{j}[\mathsf{k}_{i}]\right) Σi=((1−ωij)Pi−1[𝗄i]+ωijPj−1[𝗄i])−1,x̂i[𝗄i]=Σi((1−ωij)Pi−1[𝗄i]x̂i[𝗄i]+ωijPj−1[𝗄i]x̂j−1[𝗄i]),Pi[𝗄i]=Σi.\begin{aligned} \Sigma_{i} &= \left((1-\omega_{ij})P_{i}^{-1}[\mathsf{k}_{i}] + \omega_{ij}P_{j}^{-1}[\mathsf{k}_{i}]\right)^{-1},\\ \hat{x}_{i}[\mathsf{k}_{i}] &= \Sigma_{i} \left((1-\omega_{ij})P_{i}^{-1}[\mathsf{k}_{i}]\hat{x}_{i}[\mathsf{k}_{i}] + \omega_{ij}P_{j}^{-1}[\mathsf{k}_{i}]\hat{x}_{j}^{-1}[\mathsf{k}_{i}]\right),\\ P_{i}[\mathsf{k}_{i}] &= \Sigma_{i}.\end{aligned}

2.2.2.3 Ellipsoidal Intersection

The fusion method EI results in a “smaller” error covariance compared to CI, as the fusion result is not a convex combination of prior estimate. Instead, EI finds an explicit expression of the (unknown) correlation before merging independent parts of xix_{i} and xjx_{j} via algebraic fusion formulas. To that extent, the (unknown) correlation is characterized by a mutual covariance Γij∈ℝn×n\Gamma_{ij} \in \mathbb{R}^{n \times n} and a mutual mean γij∈ℝn\gamma_{ij} \in \mathbb{R}^{n}, yielding the following inner function Ω(⋅,⋅,⋅,⋅)\Omega(\cdot,\cdot,\cdot,\cdot):

EI: (x̂i[𝗄i],Pi[𝗄i])=Ω(x̂i[𝗄i],Pi[𝗄i],x̂j[𝗄i],Pj[𝗄i])(\hat{x}_{i}[\mathsf{k}_{i}],P_{i}[\mathsf{k}_{i}]) = \Omega\left(\hat{x}_{i}[\mathsf{k}_{i}], P_{i}[\mathsf{k}_{i}], \hat{x}_{j}[\mathsf{k}_{i}], P_{j}[\mathsf{k}_{i}]\right) Σi=(Pi−1[𝗄i]+Pj−1[𝗄i]−Γij−1)−1,x̂i[𝗄i]=Σi(Pi−1[𝗄i]x̂i[𝗄i]+Pj−1[𝗄i]x̂j−1[𝗄i]−Γij−1γij),Pi[𝗄i]=Σi.\begin{aligned} \Sigma_{i} &= (P_{i}^{-1}[\mathsf{k}_{i}] + P_{j}^{-1}[\mathsf{k}_{i}] - \Gamma_{ij}^{-1})^{-1},\\ \hat{x}_{i}[\mathsf{k}_{i}] &= \Sigma_{i} \left(P_{i}^{-1}[\mathsf{k}_{i}]\hat{x}_{i}[\mathsf{k}_{i}] + P_{j}^{-1}[\mathsf{k}_{i}]\hat{x}_{j}^{-1}[\mathsf{k}_{i}] - \Gamma_{ij}^{-1}\gamma_{ij}\right),\\ P_{i}[\mathsf{k}_{i}] &= \Sigma_{i}.\end{aligned}

The mutual mean γij\gamma_{ij} and mutual covariance Γij\Gamma_{ij} are found by a singular value decomposition, which is denoted as [S,D,S−1]=svd(Σ)[S,D,S^{-1}] = \text{svd}(\Sigma) for a positive definite Σ∈ℝn×n\Sigma \in \mathbb{R}^{n \times n}, a diagonal D∈ℝn×nD \in \mathbb{R}^{n \times n} and a rotation matrix S∈ℝn×nS \in \mathbb{R}^{n \times n}. As such, let us introduce the matrices Di,Dj,Si,Sj∈ℝn×nD_{i},D_{j},S_{i},S_{j} \in \mathbb{R}^{n \times n} via the singular value decompositions [Si,Di,Si−1]=svd(Pi[𝗄i]),[Sj,Dj,Sj−1]=svd(Di−12Si−1Pj[𝗄i]SiDi−12).\begin{aligned} \left[S_{i},D_{i},S_{i}^{-1}\right] &= \text{svd}\left(P_{i}[\mathsf{k}_{i}]\right), \\ \left[S_{j},D_{j},S_{j}^{-1}\right] &= \text{svd}\left(D_{i}^{-\frac{1}{2}}S_{i}^{-1}P_{j}[\mathsf{k}_{i}]S_{i}D_{i}^{-\frac{1}{2}}\right).\end{aligned} Then, an expression of γij\gamma_{ij} and Γij\Gamma_{ij}, for some ς∈ℝ>0\varsigma \in \mathbb{R}_{>0} and {A}qr∈ℝ\{A\}_{qr} \in \mathbb{R} denoting the element of a matrix AA on the qq-th row and rr-th column, yields DΓij=diag(max[1,{Dj}11],⋯,max[1,{Dj}nn]),Γij=SiDi12SjDΓijSj−1Di12Si−1,γij=(Pi−1+Pj−1−2Γij−1+2ςIn)−1×((Pj−1−Γij−1+ςIn)x̂i+(Pi−1−Γij−1+ςIn)x̂j).\begin{aligned} D_{\Gamma_{ij}} &= \text{diag}\left(\max[1,\{D_{j}\}_{11}], \cdots, \, \max[1,\{D_{j}\}_{nn}]\right),\\ \Gamma_{ij} &= S_{i}D_{i}^{\frac{1}{2}}S_{j} D_{\Gamma_{ij}} S_{j}^{-1}D_{i}^{\frac{1}{2}}S_{i}^{-1},\\ \gamma_{ij} &= \left( P_{i}^{-1} + P_{j}^{-1} - 2\Gamma_{ij}^{-1} + 2\varsigma I_{n}\right)^{-1} \times \\ & \quad \left(\left(P_{j}^{-1} - \Gamma_{ij}^{-1} + \varsigma I_{n}\right)\hat{x}_{i} + \left(P_{i}^{-1} - \Gamma_{ij}^{-1} + \varsigma I_{n}\right) \hat{x}_{j}\right).\end{aligned} A suitable value of ς\varsigma follows: ς=0\varsigma = 0 if |1−{Dj}qq|>10ϵ|1-\{D_{j}\}_{qq}| > 10 \epsilon, for all q∈ℤ[1,n]q \in \mathbb{Z}_{[1,n]} and some ϵ∈ℝ>0\epsilon \in \mathbb{R}_{>0}, while ς=ϵ\varsigma = \epsilon otherwise. The value 10 is used in this work to define that the value is much larger, and combined with a design parameter ϵ\epsilon support a numerically stable result.

This completes the description of the estimation function depicted in Figure 2.2. Let us continue by explaining the reconfiguration parameters that can be tuned for the considered estimation function.

2.2.3 Tuning the Functional Primitives

The estimation function illustrated in Figure 2.2 consists of two functional primitives. A node ii combines received measurements 𝕐j\mathbb{Y}_{j} via the Kalman filtering functional primitive fKFf_{\text{KF}}, while received estimates 𝕏j\mathbb{X}_{j} are merged in the functional primitive fMEf_{\text{ME}} via either SY (synchronization), CI (covariance intersection) or EI (ellipsoidal intersection). There are several parameters and structural changes that the management layer can select, so that a suitable estimation function is constructed in line with the current situation and available resources. The different options for tuning a functional primitive are addressed in this section.

Sampling time τi\tau_{i}: The sampling time of both primitives fKFf_{\text{KF}} and fMEf_{\text{ME}} can be tuned accordingly. At every sample time the Kalman filter executes and provides a new local estimate. Then, the merging function is triggered, merging any received estimates into a regional estimation. Lowering the sampling time τi\tau_{i} implies that estimation accuracy, computational demand and data exchange will be decreased, i.e., saving communication and computational resources and thereby saving energy.

Shared data 𝕐j\mathbb{Y}_{j} and 𝕏j\mathbb{X}_{j}: The selection of which variables are shared, i.e., (yi,Ci,Vi)(y_{i},C_{i},V_{i}) and/or (x̂i,Pi)(\hat{x}_{i},P_{i}), can change in time. Exchanging both improves estimation results throughout the network but requires communication resources. Decreasing the usage of this resource can be done by exchanging either the local measurement or the local estimation result, which would yield a decrease in the estimation accuracy. Additionally, the frequency of exchanging data can be influenced by changing the communication frequency parameter fif_{i}.

Implemented algorithm: There is only one implementation of the functional primitive fKFf_{\text{KF}}, which is the Information filter. Yet, for the merging primitive fMEf_{\text{ME}} one has the option between three alternative implementations—only one of which can be active in a node at any given time:

SY: The inner-function Ω(⋅,⋅,⋅,⋅)\Omega(\cdot,\cdot,\cdot,\cdot) is characterized by the synchronization approach. The required computational power for this alternative is low, though it would result in a poor estimation accuracy as well;

CI: The inner-function Ω(⋅,⋅,⋅,⋅)\Omega(\cdot,\cdot,\cdot,\cdot) is characterized by the covariance intersection approach (Julier and Uhlmann 1997). The required computational power for this alternative is moderate and would result in a moderate estimation accuracy;

EI: The inner-function Ω(⋅,⋅,⋅,⋅)\Omega(\cdot,\cdot,\cdot,\cdot) is characterized by the ellipsoidal intersection approach (Sijs and Lazar 2012). The required computational power for this alternative is high and would result in a high estimation accuracy;

The above options on changeable parameters and alternative functional primitive are exploited by the management layer for finding a match between the desired estimation quality (accuracy) and the required resources.

2.3 Reconfiguration Framework

The following reconfiguration framework provides the tools needed for a self-organizing state estimation sensor node. We use concepts from model-based design in runtime to aid the reconfiguration process by providing information about potential configuration states. A reasoner can then compare different states, and implement the most beneficial one.

2.3.1 Model-Based Design Concepts

The design challenge for any embedded system is to realize the required functionalities (in this case state estimation) on a given hardware platform while satisfying a set of nonfunctional requirements, such as response times, dependability, power efficiency, etc. Model-based system design has been proven to be a successful methodology for supporting the system design process (Karsai and Sztipanovits 1999). Model-based methodologies use multiple models to capture the relevant properties of the design. These models can then be used for various purposes, such as automatic code generation, design optimization, system evolution, etc. (Karsai et al. 2010) Crucial for the design process are the interactions between the different models.

Two fundamental models of the design are (i) the task model, capturing the required functionalities of the employed signal processing method, and (ii) the physical model capturing the hardware configuration of the implementation. In Figure 2.3 the task model is represented as directed a graph: the signal processing components are represented by the vertices of the graph, while their data exchange or precedence relations are represented by the edges. Both the tasks and the interactions are characterized by a set of properties, which typically reflect non-functional requirements/properties. The tasks run on a connected set of processors, represented by the physical model of the system. The components in the physical model are the computing nodes and the communication links.

Figure 2.3: The task and physical model represent the different functional components and the processing components where they can run, respectively. A mapping between them defines which functions run where.

It should be mentioned that in the signal processing context the task graph is designed in two phases as shown in Figure 2.4: first the functional primitives are connected to form the signal flow graph satisfying the functional requirements and design constraints. Then, the task network should be created via clustering the elements of the network of functional primitives to tasks considering computation, communication and temporal requirements. This is not a linear process and there is a strong dependency on the physical configuration. Moreover, the search and optimization in the design space make this an iterative process, which requires interactions between hardware, software and signal processing architecture designs.

The design process involves finding a particular mapping that defines the assignment of a task TqT_q to a processor PiP_i, i.e., it determines which task runs on which node. Obviously the memory and execution time requirements define constraints when assigning the tasks to nodes. Further, data exchange between tasks makes the assignment problem more challenging in distributed configurations, as a task assignment also defines the use of communication links cijc_{ij} - and the communication links have limited capacities. The design process results in a sequence of decisions, which lead to a feasible system design. Traditionally this design process is “off-line,” i.e., it is completed before the implementation and deployment of the system itself. The task model, the hardware configuration and their characteristics are assumed to be known during this design time and the design uncertainties are assumed to be low.

Figure 2.4: The design flow of the signal processing system; the function network influences the design choices of the task network.

2.3.2 Runtime Reconfiguration

These are overly optimistic assumptions for large-scale sensor and actuator (control) networks: in many cases they are deployed in “hostile” environments, where component failures and dynamically changing configurations manifest themselves as common operational events. Expressed in the concepts of Figure 2.3, conceptually the runtime reconfiguration is carried out via changing the task graph (i.e. selecting a different signal processing scheme, changing certain parameters of the functional primitives, etc.) or re-mapping the task graph to the physical model (i.e. changing the task assignment with the consequential change in the communication topology).

As Figure 2.1 already indicates, our goal is to realize the reconfiguration functionality for distributed state estimation to improve robustness and scalability. The functional scheme of the reconfiguration is shown in Figure 2.5. The primary functionality (in our case the state estimation) is realized by the task network (via the invocation of associated function primitives). The task network is built during initialization time according to (off-line) design specification. The reconfiguration runs parallel to the primary data stream: based on the execution status (e.g. quality of the results generated, the conditions of the hardware resources, the availability of the communication links, etc.) the reconfiguration functionality makes decisions about the configuration, its parameterization and resource usage in order to satisfy the given requirements and constraints. The reconfiguration is event driven, triggered by changes in the execution context or the changing (user) requirements and constraints. The reconfiguration may act on the software side (e.g. selecting a different algorithm to implement a particular functional primitive, changing task allocation, etc.) or on the hardware side (e.g. adjusting transmission power, suspending/awaking components, etc.).

Figure 2.5: A schematic representation of the reconfiguration process. The primary data path is updated by a secondary “management” layer by updating the structure or parameters. The nodes’ reconfiguration components can coordinate with one another to find configuration that are mutually beneficial.

The following characteristics of the proposed scheme should be emphasized:

Every time instant the function/task network is a snapshot of the possible variants and mappings. Alternatives may not be explicitly enumerated but can be the result of a reasoning process.

The scheme explicitly supports the separation of concerns principle; reconfiguration mechanisms can be designed and implemented relatively independently.

The reconfiguration can be a resource demanding activity. Therefore, the scheme allows for tuning the “intelligence level” of the reconfiguration depending on the performance of the hardware configuration—virtually leaving the signal processing aspect uninfluenced.

There are low-overhead implementations available for dynamic data-flow graph based signal processing (e.g. (Nordstrom, Sztipanovits, and Karsai 1998)). Consequently, the influence of the reconfiguration on the signal processing performance can be kept low. The interfacing between the data-flow graph and the “management” side is usually implemented by a simple API or message passing mechanism.

The scheme is not specific to the distributed state estimation problem, but other signal processing tasks including control or other multi-agent based tasks can be mapped into this framework as well.

The scheme is applicable to reconfiguration on “various levels of granularity”: task, node and system levels, i.e. the reconfiguration strategy scales from fine grade distributed to a centralized one. Needless to say distributed reconfiguration may need cooperation among the reconfiguration functionalities.

From execution point of view the reconfiguration functionalities should be included in the task graph (as one or more cooperating tasks) and their resource demand should be accounted for.

In the following the “management” side will be further detailed. The representation of the configuration and the design knowledge as well as the associated reasoning mechanisms are the key elements on the management layer, thus in the following these aspects will be emphasized.

2.3.3 Knowledge Representation and Reasoning

For the management layer as seen in Figure 2.1, which reconfigures the core tasks’ functionality, a three-step strategy is implemented. The first step in reconfiguration is the monitoring step, in which the current status quo is observed, in order to reflect the system’s own health/performance and the state of the embedding environment. The second step is the reasoning step in which the observed characteristics are analyzed, decided whether reconfiguration is even required, and if it is required how to do so. The final step is the actuation step which performs the decisions made in step two, thereby completing the reconfiguration process.

The reasoning step is one of special interest, because it is mainly here where the intelligence about the configuration is represented in the system. Because the reasoning is only a single step within the reconfiguration process and it always operates with a predefined interface, it can be separated from the rest of the system which makes it relatively easy to implement any kind of reasoning module.

In order to reconfigure the tasks’ core functionality, the reconfigurator requires knowledge and a method for reasoning about the various configurations. These two are intrinsically connected since the form of the knowledge representation depends on the method of reasoning. A case-based reasoner would require knowledge in terms of different complete configurations, whereas a utility reasoner would require a utility function.

From the many forms of reasoning and knowledge representations, for this article a first order logic (FOL) reasoner will be used. The corresponding knowledge representation exists of a rule base existing of atoms representing the configurable parameters, and constraints and conditions in the form of logical compound statements to determine what parameter choices are valid and which are not. The problem statement of reconfiguration is now reduced to finding the values for the atoms that satisfy the statements (effectively a search). Now, problem solving methods can be used for solving FOL problems such backtracking and the Selective Linear Definite clause resolution which is proven to be sound and complete (Stärk 1989; Apt and Bol 1994; Ben-Ari 2012).

FOL has been used to describe reconfiguration knowledge in the past as well (Endler and Wei 1992; Simonot and Aponte 2009). An important reason for this is that FOL reasoners have proven to be very expressive in that they can describe both conditions and constraints, perform boolean, numerical and symbolical operations and therefore can reconfigure either by optimizing parameters or starting/stopping components (Bradbury et al. 2004).

Using a FOL reasoner however, also means that a priori to deploying the system, all constraints and conditions must be determined because a rule base is required by the reasoner. This requires some design time knowledge which can be expert or empirical knowledge from experiments. For scenarios in which multiple methods are applicable, a preferential order must be determined. More complex bias-free reasoners, which are capable of taking into account the effect of one’s choice on neighboring nodes, will be looked into in the next chapter.

2.4 Case Study

In the case study, the proposed framework is applied to a scenario in which the temperature distribution of a greenhouse has to be monitored. In the scenario there are NN nodes all equipped with a temperature sensor, and a communication interface for communicating wirelessly. Each node had to compute an estimate the global greenhouse temperature distribution based on a local measurement and communication with the other nodes. The implementation of the experiment was in the form of a discrete event simulation (de Filho et al. 2013).

Using off-line measurements from a real physical small scale greenhouse setup, the system had access to realistic data, but over multiple runs, the sensors would obtain the same input. In the experiment, the six simulated nodes are equipped with simple temperature sensors, which would base their measurements on the values from this database.

The nodes were constrained in the bandwidth of the communication with other nodes, the amount of integer and floating-point operations per second (IOPS/FLOPS) and a limited energy supply. In the ideal situation these constraints should imply that the node should initially use the most “expensive” method that would be computationally feasible, and under decreasing battery capacity would decrease its effort, and in the end use the “cheapest” method. At the same time the system would always employ methods that satisfy the current bandwidth conditions.

In the scenario implemented for this experiment, there are six nodes and in one of the nodes the monitor finds the battery level to drop below a certain threshold, such that reconfiguration is desired. In the experimental setup the system can change the following variables:

the algorithm used for the functional primitive fMEf_{\text{ME}}, which can be either EI, CI or SY,

the sampling rate at which to sample the sensor τi\tau_{i},

the communication rate to send out information to neighboring nodes fif_{i},

the sleep time of the radio, which controls the rate of incoming messages from neighboring nodes f′if'_{i}.

In the initial configuration the system uses EI in the merging functional primitive, samples its sensor once every 60 seconds and broadcasts its state estimation results every 90 seconds. Furthermore, it fires the monitoring cycle every 150 seconds and shuts down the radio for 5 seconds every other 30 seconds (thereby using a pattern of 5 seconds sleep, followed by 25 seconds receiving.) Exchanged variables are automatically chosen, so that if a node uses EI or CI it broadcasts (x̂i,Pi,𝗄i,i)(\hat{x}_{i},P_{i},{\textsf{k}}_{i},i) whereas if it uses SY it broadcasts (x̂i,𝗄i,i)(\hat{x}_{i},{\textsf{k}}_{i},i).

The reasoner implemented relies on a Prolog based FOL interpreter1. Choosing this implementation has a couple of additional advantages. First and foremost, it has been used for a long time by experts for formally defining expert knowledge (Rossi 1986), and is very expressive, but also flexible in the type of rules that could be used to describe the knowledge for the application. Secondly, Prolog is a well-known logical programming language and therefore the framework can easily be programmed using existing syntax and methods. Finally, the Prolog implementation can use an external rule base, separating the reasoning rule base from the implementation itself. This results in having the reconfiguration behavior defined separately and independently of the rest of the system.

Figure 2.6: The error covariance trace of nodes 3 and 6, when changing the merging algorithm in node 3 from Ellipsoidal Intersection to Covariance Intersection.

Figure 2.7: The error covariance trace of nodes 3 and 6, when decreasing the outgoing communicating frequency in node 3 to 25%.

The knowledge of the reconfiguration reasoner must be coded a priori to the deployment of the system. The constraints and conditions of the rules, and the order in which the different reconfiguration actions will be performed must be determined. This does not mean that the system will reconfigure in any specific order, because the operating conditions are unknown beforehand, and therefore the constraints and conditions determine the configuration at runtime.

The FOL rule base allows for a wide range of rule types. The rule base created for the case study contained rules of varying complexity, from very simple rules considering the choice of parameters to more complex rules combining different conditions of system properties into a desired reconfiguration action. Example statements would formally be implemented in Prolog as following:

Example Prolog reconfiguration statements

  idealSamplingFrequency(0.2).

  batteryCritical(State) :-
    getBatteryLife(State, ~BatteryLife),
    minBattery(Threshold),
    BatteryLife < Threshold.

  action(lowerCommunicationFrequency, ~State, ~Reason) :-
    batteryLow(State),
    \+ communicationFrequencyLow(State),
    Reason = "The battery is low and the communication frequency is high enough.".

  suggest(NewSetting, lowerSamplingFrequency, State) :-
    samplingFrequencyLow(State),
    getSamplingFrequency(State, SamplingFrequency),
    NewSetting is SamplingFrequency * 0.75.

Figure 2.8: The error covariance trace of nodes 3 and 6, when changing the radio sleep time in of node 3 to 50%, effectively decreasing the incoming communication frequency.

Figure 2.9: The estimated remaining battery life of nodes 3 and 6, when changing the radio sleep time. Here, the reduction of power consumption of the radio is very noticeable.

Whenever a re-parametrization is in order, the reasoner also has to provide the system with the new parameters. The last statement in the above example shows an example of how the choice of parameters might be implemented. Note that this way of choosing the parameters means that the system will act like a feedback loop. In order to find an optimal new value, another type of reasoner will have to be implemented such as a utility based reasoner.

In order to determine the ordering of the different type of configurations and to create the related rule base, decision were made upfront by the system designer by experimentally trying out different configurations. In these experiments the six nodes would operate, and after two hours of simulation time, the configuration of Node 3 would change. For the results of these experiments, see Figures 2.6 through 2.8. In Figure 2.6 it can be seen that changing the fusion method has a significant impact on the error covariance of the state estimation in reconfigured node, but also in the node that stays the same. The same holds for a change in the outgoing communication frequency fif_{i}, of which the results can be seen in Figure 2.7. The sleep time of the radio has relatively the smallest impact, and seems the best option for the first reconfiguration action. This means the node will receive fewer messages from the other nodes and therefore the error covariance will go up, but much less than with any of the other options. Using this information, a rule base can be created.

When running the resulting system with the created rule base in a simulated experiment, the reconfiguration reasoner will deduce that a different sleep time is most desirable. In Figure 2.9 it can be seen that the corresponding remaining battery lifetime goes up significantly.

2.5 Conclusions

In this chapter a framework was proposed to implement self organization in a sensor network. We defined a framework for distributed state estimation using a collection of functional primitives that can be redeployed, reconnected and parameterized by a management layer. This introduces the possibility to reason about the configuration of how to do state estimation under a variety of circumstances and user requirements.

In the greenhouse case study we have shown that the proposed framework is capable of improving the battery lifetime of a sensor by runtime reconfiguring the state estimation method, while maintaining a good performance level. This is done by modifying the outgoing frequency, and the sleep period parameters for the communication strategy, and thereby having minimal impact on the state estimation error. However, in this chapter we only considered the state estimation problem, whereas the framework allows for reconfiguring all kinds of distributed reasoning tasks. In the later chapters we will look at different problem domains, e.g. wireless power transfer in Chapter 4 and smart grids in Chapter 6.

The modular framework allows for easy implementation of a different reasoning engine, but also for portability for different state estimation tasks. In the current reasoner, a first-order logic core uses an a priori determined set of ordered rules from the rule base. This is a drawback of the logic-based reasoner, and in a real implementation it would be recommendable to use an unbiased context-free configuration space exploring reasoner. An example of this could be a genetic algorithm adapted to the reconfiguration scenario, or a learning algorithm. Another drawback of the current reasoner is the lack of coordination among nodes; although this could be implemented in a logic based reasoner, this has not been done in this chapter. To address this shortcoming, in the next chapter a DCOP-based method for orchestrating configurations among different nodes is proposed, for coordinated decision-making such that all nodes benefit.

http://www.gnu.org/software/gnuprologjava/↩︎

3 CoCoA: an (A)DCOP Solver

3.1 Introduction

Self-organization is a property of a group of systems that can adapt their behavior to changing environments, or user requirements. In Chapter 1, we introduced the notion of self-organization either through emergent behavior, or through explicit cooperation. In Chapter 2, we introduced a framework for reconfiguring a system’s deployment, but when we reason about how the system should be configured, we can either make decisions locally (thus using the emergent behavior approach), or use a distributed decision-making method. Local reasoning about an agent’s behavior is definitely feasible, as we have shown in the previous chapter. It is however, much more challenging to adapt while keeping in mind the effect of a single agent’s decisions on the group as a whole. In order to make sure the agents act as a group, decisions need to be coordinated or orchestrated. However, the traditional approach using a central coordinator is not desirable, since it leads to a single point of failure and does not scale well. Without a central coordinator or hierarchy, the agents need to collaborate as peers in order to make sure the group objective is maintained.

Distributed Constraint Optimization Problems (DCOP) is a class of optimization problems in which discrete variables are controlled by distributed agents and the optimization function itself operates over the complete set of variables (Hirayama and Yokoo 1997). This class of problems allows to formalize the type of decisions a group of agents needs to make in a coordinated fashion. By definition of DCOP, the involved agents are part of a team and need to cooperate in order to perform well on the global task. Usually in DCOPs, cooperation between agents is achieved by passing messages from one agent to another. DCOPs are encountered in many fields such as in wireless LAN channel allocation (Yeoh and Yokoo 2012), coordination of mobile sensing teams (Yedidsion, Zivan, and Farinelli 2014) or coordination of tasks (Farinelli et al. 2008).

A number of complete algorithms have been proposed to find the optimal solution of a DCOP, amongst which are ADOPT (Modi et al. 2005), DPOP (Petcu and Faltings 2005a), NCBB (Chechetka and Sycara 2006) and Asynchronous Forward Bounding (Gershman, Meisels, and Zivan 2009). However, DCOP problems are NP-hard (Modi 2003), so the effort to find the optimal solution becomes intractable for increasingly large-scale problems. Therefore, incomplete DCOP algorithms trade a distance from the optimal solution for convergence speed and are thus more suited for large-scale problems. Examples of incomplete DCOP solvers are DBA (Yokoo et al. 1998), DSA (Fitzpatrick and Meertens 2003), max-sum (Farinelli et al. 2008), MGM and MGM-2 (Maheswaran, Pearce, and Tambe 2004). Also, a combination of an incomplete solver, with a complete solver is proposed in a hybrid strategy called HS-CAI (D. Chen et al. 2020).

Recently, an extension on the DCOP framework has been described in which agents may value a set of constrained assignments differently. In these Asymmetric DCOPs (ADCOP) constraints have different costs for their agents. The ACLS and GCA-MGM algorithms (Grubshtein et al. 2010; Grinshpoun et al. 2013) have been proposed to enable solving this class of problems. More recently, it has also been shown that the max-sum_ADVP algorithm can solve ADCOPs (Zivan, Parash, and Naveh 2015). In solving ADCOPs there is usually a trade-off in privacy versus optimality (Deng et al. 2019).

Most existing DCOP algorithms use an iterative approach, which requires many rounds of message passing during the optimization process, and thus require a relatively large communication overhead. In this chapter we present a case study in which this communication overhead is especially important: to find an optimal configuration of a sensor network, tasked with monitoring the cargo of a shipping container for an extensive period of time. Since in sensor networks communication between nodes has the largest influence on the battery lifetime, we need to minimize the communication between nodes during the optimization process, and require an algorithm that is guaranteed to converge to a solution as quickly as possible.

We will introduce a new (A)DCOP algorithm, denoted as Cooperative Constraint Approximation (CoCoA), which uses a non-iterative, semi-greedy approach with a single step lookahead (SSLA). We show that it finds high quality solutions much faster than other (A)DCOP solvers, using far fewer system resources. Experimentally, we show that in some cases this leads to a reduction of up to two orders of magnitude in the number of transmitted messages and cost function evaluations, thus leading to superior running times.

3.2 DCOP: Problem Statement and Challenges

DCOPs are defined as a tuple 𝒯=⟨𝒜,𝒳,𝒟,ℛ⟩\mathcal{T}=\langle \mathcal{A}, \mathcal{X}, \mathcal{D}, \mathcal{R}\rangle in which 𝒜\mathcal{A} is a finite set of agents {A1,A2,…,An}\{A_{1}, A_{2}, \ldots, A_{n}\} and 𝒳\mathcal{X} is a finite set of variables {X1,X2,…,Xn}\{X_{1}, X_{2}, \ldots, X_{n}\} with finite discrete domains {D1,D2,…,Dn}\{D_{1},D_{2},\ldots,D_{n}\} from 𝒟\mathcal{D} such that Xi∈DiX_{i} \in D_{i}. Each agent AiA_{i} is assigned one variable XiX_{i}, and therefore |𝒜|=|𝒳|=|𝒟||\mathcal{A}| = |\mathcal{X}| = |\mathcal{D}|. Then, ℛ\mathcal{R} is a set of relations (constraints) in which each constraint C∈ℛC\in \mathcal{R} defines a non-negative cost. For DCOPs such costs are defined for every possible value assignment of a set of variables C:Di1×Di2×…×Dik→ℝ≥0C{:~} D_{i_1} \times D_{i_2} \times \ldots \times D_{i_k} \to \mathbb{R}_{\geq 0}, while for ADCOPs each constraint defines a set of costs for each involved variable, i.e. C:Di1×Di2×…×Dik→ℝ≥0kC{:~} D_{i_1} \times D_{i_2} \times \ldots \times D_{i_k} \to \mathbb{R}_{\geq 0}^{k}. Having all definitions of 𝒯\mathcal{T}, in (A)DCOPs the goal of the agents is to minimize the global cost function, i.e. arg min𝒳∑ℛ.\underset{\mathcal{X}}{\text{arg min}} \sum{\mathcal{R}}. In the rest of this chapter we shall only take into account binary constraints, in which exactly two variables are considered, of the form Ci,j:Di×Dj→ℝ≥02C_{i,j}{:~}D_{i} \times D_{j} \to \mathbb{R}_{\geq 0}^{2}. Note that the constraints between variables can be shown as an undirected graph, for example as shown in Figure 6.2.

Definition 3.1 (Neighbors). We refer to agents as neighbors if there is a constraint between their corresponding variables. This follows the real-life situation of limited range between agents, e.g. communication range in wireless networks. The set of all neighbors of an agent ℳi⊆𝒜\mathcal{M}_{i} \subseteq \mathcal{A} is called the neighborhood.

Definition 3.2 (Current Partial Assignment). The set 𝒳̂i\hat{\mathcal{X}}_{i} denotes the set of known assigned values of the neighbors of AiA_{i} and is also referred to as the current partial assignment (CPA).

Definition 3.3 (Non-Iterative Algorithm). A non-iterative algorithm is one that does not rely on multiple rounds (iterations) of value assignments, or information sharing between agents, until some stopping criterion is met. A non-iterative algorithm is by definition asynchronous; it does not rely on synchronous activation certain phases of the algorithm, instead, the activation of agents happens sequentially triggered by local interactions.

Figure 3.1: Example of a constraint graph in a graph coloring problem with six agents (vertices), variables (colors), and nine constraints (edges) between them.

3.2.1 DCOP: Existing Solvers

DCOP solvers can be categorized into complete and incomplete. Complete solvers search the entire solution space and are guaranteed to find the optimal solution, while incomplete solvers try to find a “good” solution in a reasonable time.

Incomplete solvers from literature, e.g. DSA (Fitzpatrick and Meertens 2003), MGM-2 (Maheswaran, Pearce, and Tambe 2004), DALO (Kiekintveld et al. 2010) or GCA-MGM (Grubshtein et al. 2010) are local search algorithms, trying to approximate the global function by solving a local problem. DSA is known for its low communication overhead and its ability to find high quality solutions for symmetric DCOPs (Pearce and Tambe 2007), whereas ACLS and GCA-MGM can also solve ADCOPs.

The max-sum algorithm (Farinelli et al. 2008) is another incomplete solver, that works in a completely different manner. It operates on a bipartite graph, separating variable from constraint nodes, and spreads information through the graph to estimate the effect of value assignments. It is capable of finding optimal solutions, but only when the graphs contain no cycles (Cohen and Zivan 2017). The max-sum algorithm will converge to the optimal solution on acyclic graphs (Cohen and Zivan 2017).In order to deal with cyclic graphs and asymmetric costs, variations of the algorithm have been proposed to deal with cyclic graphs such as max-sum_ADVP (Zivan and Peled 2012) or with asymmetric problems (Zivan, Parash, and Naveh 2015), but is then no longer guaranteed to find the optimal solution. Max-sum and the local search algorithms apply an iterative approach; they evaluate their performance, share information, update their variable, and repeat until a stopping criterion is met—usually a predetermined number of iterations.

3.2.2 Challenges

In this chapter we propose an algorithm capable of solving (A)DCOPs with a minimal communication and computation overhead. We hypothesize we can achieve this by not iteratively sending messages and updating the variable, but instead using a greedy, SSLA approach. This means that each agent takes a decision based on information only from its direct neighbors and will activate agents sequentially. Under these circumstances we need to address the following challenges:

Challenge 1: Premature Assignment A non-iterative DCOP solver assigns a value to a variable only once. In its most simple form an agent would only look at its local constraint costs and the known values of its neighbors. It would select a value that minimizes its local cost and update its variable. Greedy algorithms have the advantage of converging very fast, but early choices may turn out to be suboptimal when neighbors have assigned their value.

Challenge 2: Synchronization When two neighbor agents are both deciding for a new value a race condition may occur, i.e. the outcome of one agent arrives too late for the other agent’s decision. For iterative algorithms this is not an issue since in a later iteration one agent can correct for any incorrect assumptions; for non-iterative solver this is not possible.

Challenge 3: Asymmetric Costs An incomplete solver may end up in a local minimum if a local beneficial assignment leads to poor global results. An agent may assign a variable to decrease its local cost, but potentially increases the cost of its neighbors. This over-greediness may cause the global cost to increase or lead to unstable solutions. In strongly asymmetric constraints for every combination of value assignments at least one agent can improve its local cost by shifting to another assignment without decreasing the global cost. Under these circumstances iterative solvers may not converge to the minimum where both agents are assigned the same value, but agents on either side of the constraint will maintain a cycle of assigning different values to improve their local cost.

3.3 CoCoA: A New DCOP Solver

To address the challenges introduced in the previous section we propose a new incomplete ADCOP algorithm based on a semi-greedy strategy, denoted as Cooperative Constraint Approximation (CoCoA), employing three key ideas:

A single step lookahead (SSLA) to consider the effect of an assignment on the cost of neighbors. This is especially effective when a neighbor is constrained in its choices;

A unique-first approach, such that an agent will only assign a value if it is a unique local optimum for its variable. If it cannot find a unique solution, the decision will be delayed until more information is available;

A state machine to spread and keep track of the algorithm’s activity, prevent dead-locks or endless loops.

By minimizing not only the local cost, but also the cost of its single-hop neighbors, we hypothesize that CoCoA can find a solution with a low global cost with relatively little overhead. When CoCoA is triggered it first inquires its neighbors what the effect of different assignments would be for their local cost. The neighboring agents decide the resulting cost effect asynchronously and return to the inquirer what the minimum effect would be. Upon receiving the estimated costs the active agent will assign the value that minimizes the sum of all incurred costs, including its own.

During the variable assignment process it is possible that multiple values suit equally well, especially in an early stage of the algorithm when multiple neighbors have no assigned values. In such cases the assignment will be postponed until a neighbor has changed its value. We hypothesize that this unique-first approach will help in avoiding premature convergence to a sub-optimal solution. However, this approach may lead to a deadlock if all the neighbors are waiting for each other. Therefore, we partition the algorithm in four states and have agents inform their neighbors about their internal state. When all neighbors are in the HOLD state, a bound denoting the “allowed uniqueness” is increased until a decision can be made. The proposed algorithm is given in pseudocode in Algorithm 1, with accompanying set of messages and agent states in Table 3.1 and Table 3.2, respectively and discussed in detail in the subsequent section.

Remark 3.1. Due to its non-iterative approach, it is impossible to recover from early choices. This may lead to situations in which a variable must be set to a value that leads to a very high cost, i.e. it has to break a hard constraint.

Algorithm 1: CoCoA Algorithm

| When started or upon receiving UpdState(j{j}, DONE) on AiA_{i}:
| Require: state:=IDLE or state:=HOLD
1: | state←\leftarrow ACTIVE
2: | send ∀Aj∈ℳi\forall A_{j} \in \mathcal{M}_{i} UpdState(i{i}, ACTIVE)
3: | send ∀Aj∈ℳi\forall A_{j} \in \mathcal{M}_{i} InqMsg(i{i}, 𝒳̂i\hat{\mathcal{X}}_{i})
4: | wait for all CostMsg(Θj\Theta_{j})
5: | find δ\delta using [eq:aaai:minsum]
6: | if 𝒰(Xi)≤β\mathcal{U}(X_{i}) \leq \beta or number of idle/active neighbors is 0 then
7: |     Xi←X_{i} \leftarrow random from Xi,δX_{i,\delta}
8: |     state←\leftarrow DONE
9: |     send ∀Aj∈ℳi\forall A_{j} \in \mathcal{M}_{i} UpdState(i{i}, DONE)
10: |     send ∀Aj∈ℳi\forall A_{j} \in \mathcal{M}_{i} SetVal(i{i}, 𝒳̂i\hat{\mathcal{X}}_{i})
11: | else
12: |     state←\leftarrow HOLD
13: |     send ∀Aj∈ℳi\forall A_{j} \in \mathcal{M}_{i} UpdState(i{i}, HOLD)
14: | end if
| Upon receiving InqMsg(i{i}, 𝒳̂i\hat{\mathcal{X}}_{i}) at AjA_{j}:
15: | incorporate 𝒳̂i\hat{\mathcal{X}}_{i} in 𝒳̂j\hat{\mathcal{X}}_{j}*^*
16: | for allXi,k∈DiX_{i,k} \in D_{i}
17: |     find Θj,k\Theta_{j,k} using [eq:aaai:localmin]
18: | end for
19: | Send AiA_{i} CostMsg(Θj\Theta_{j})
| Upon receiving UpdState(i{i}, S):
20: | Store state SS of neighbor AiA_{i}
21: | ifSS is HOLD and my state is HOLD and number of idle/active neighbors is 0 then
22: |     β\beta++
23: |     Repeat algorithm
24: | else if S is DONE and my state is HOLD then
25: |     Repeat algorithm.
26: | end if

*^*This line is added since the original publication for clarity; the implementation did not change.

3.3.1 CoCoA: Algorithm Description

CoCoA assumes that all neighbors AiA_{i} can communicate with, ℳi\mathcal{M}_{i}, are known. Also, each Aj∈ℳiA_{j} \in \mathcal{M}_{i} must know its neighbor’s domain DiD_{i}. Finally, we assume that all nodes are reachable from any other node, i.e. for every pair of nodes there must be a set of edges that connects them.

Initially all agents start in the IDLE state and activation occurs at any random node. As soon as one agent finishes the algorithm it will trigger the algorithm for its neighbors. When any AiA_{i} has to find an assignment, it will first send an InqMsg(i{i}, 𝒳̂i\hat{\mathcal{X}}_{i}) message to its neighbors (line 3 of Algorithm 1). This will trigger agents Aj∈ℳiA_{j} \in \mathcal{M}_{i} to calculate for every possible assignment for XiX_{i} what the lowest cost would be for AjA_{j} taking into account the CPA and that assignment for XiX_{i}. That is, each Aj∈ℳiA_{j} \in \mathcal{M}_{i} calculates for every Xi,k∈DiX_{i,k} \in D_{i} Θj,k=minXj,l∈Dj∑C∈ℛjC(𝒳̂j∩Xi,k∩Xj,l),\label{eq:aaai:localmin} \Theta_{j,k} = \min_{X_{j,l} \in D_{j}} \sum_{C\in \mathcal{R}_j} C\left(\hat{\mathcal{X}}_{j} \cap X_{i,k} \cap X_{j,l} \right), where Xi,kX_{i,k} denotes that XiX_{i} is assigned the kkth value of DiD_{i}.

If variables are not yet assigned in 𝒳̂j\hat{\mathcal{X}}_{j}, the cost of their constraints can not be determined and the mean cost is used, i.e. a single step lookahead is performed. The resulting cost map Θj={Θj,1,Θj,2,…,Θj,|Di|}\Theta_{j}=\{\Theta_{j,1},\Theta_{j,2},\ldots,\Theta_{j,|D_{i}|}\} is sent via a CostMsg(Θj\Theta_{j}) back to the inquiring AiA_{i}. Then, AiA_{i} finds XiX_{i} by δ=arg mink∑j=1|ℳi|Θj,k,\label{eq:aaai:minsum} \delta= \underset{k}{\text{arg min}} \sum_{j=1}^{|\mathcal{M}_{i}|}\Theta_{j,k}, and assigning Xi,δX_{i,\delta}. The minimizing value may achieve a minimum for more than one value of XiX_{i} since the arg min\text{arg min} operator can return a set of minimizers. The uniqueness of this minimal cost is the number of distinct values that achieve this minimum, defined as 𝒰(Xi)=|δ|\mathcal{U}(X_{i}) = |\delta|. For CoCoA this means that a value can now be assigned to the variable, and for that any minimizer will do. CoCoA_UF however, differs from CoCoA in that it also employs the unique-first approach.

In CoCoA_UF the uniqueness will be compared with a bound β\beta to determine if this solution is accepted (line 6 of Algorithm 1). Initially β=1\beta=1, so that only unique solutions are accepted. If β<𝒰(Xi)\beta< \mathcal{U}(X_{i}) and at least one neighbor is ACTIVE or IDLE, the algorithm switches to the HOLD state and waits until another node has updated its state to DONE before the algorithm is run again. If an UpdState(j{j}, HOLD) message is received, indicating that the last neighbor is in the HOLD state, then β\beta is increased by one and the algorithm is repeated (line 22 of Algorithm 1). This mechanism makes sure that premature choices are avoided until more information is available. Initially, when no agents have a value assigned this may occur frequently, but as more variables are set the chances of such impasses decrease.

If 𝒰(Xi)≤β\mathcal{U}(X_{i}) \leq \beta then XiX_{i} is chosen randomly from all minimizers and is communicated to the agent’s neighbors Aj∈ℳiA_{j} \in \mathcal{M}_{i} in a SetVal(i{i}, XiX_{i}) message. This makes the neighbors AjA_{j} update their CPA (as they now know the value of XiX_{i}) and triggers the algorithm for them.

Table 3.1: List of messages sent by CoCoA

Message | Description
InqMsg(i{i}, 𝒳̂i\hat{\mathcal{X}}_{i}) | Sent by AiA_{i} at start of algorithm
CostMsg(Θj\Theta_{j}) | Neighbors’ reply; contains Θj\Theta_{j}
SetVal(i{i}, XiX_{i}) | Indicator: AiA_{i} assigned a value to XiX_{i}
UpdState(i{i}, S)* | Sent when AiA_{i} updates its state to S

*UpdState(i{i}, S) is only sent in the unique-first, CoCoA_UF variant.

Table 3.2: Agents’ potential states in CoCoA

State | Description
IDLE | Agent’s default/initial state; indicates agent is active, but not yet started.
ACTIVE | State after agent’s activation; finding an assignment for its variable.
HOLD | At an impasse; delay variable assignment and await information from neighbors.
DONE | Final CoCoA state; indicates that agent has assigned a final value to its variable.

3.3.2 CoCoA: Example Run

Let CoCoA solve a graph coloring problem, where each variable must be assigned value, which can be either blue (b), green (g), or yellow (y) such that ∀iDi={𝚋,𝚐,𝚢}\forall i D_{i} = \left\{\texttt{b},\texttt{g},\texttt{y}\right\}. The constraints in the graph coloring problem are that neighboring variables should not have the same color—a cost of one is induced for every pair of neighbors that are assigned the same color. In the example in Figure 6.2 the variables of A1A_{1}, A2A_{2}, and A6A_{6} are already assigned a color. Let us assume that this is the starting condition, and we have to find the best assignment in this situation starting at A3A_{3}. As we shall see under these premises the best solution must violate some constraints—there is no perfect solution with zero cost.

Agent A3A_{3} starts by sending UpdState(3{3}, ACTIVE) and InqMsg(3{3}, 𝒳̂3\hat{\mathcal{X}}_{3}), informing that it has started and wants to know the effect its assignment may have, to all of its single-hop neighbors Aj∈ℳ3={A1,A2,A4,A5}A_{j} \in \mathcal{M}_{3} = \{A_{1}, A_{2}, A_{4}, A_{5}\}, where 𝒳̂3={X1=𝚐,X2=𝚢}\hat{\mathcal{X}}_{3} = \{X_{1} = \texttt{g}, X_{2} = \texttt{y}\}. As these messages arrive at all the neighbors, they will save the information that is in the CPA and the state of A3A_{3}.

Each neighbor will then calculate a cost map Θj\Theta_{j}, which contains for every assignment Xi,k∈DiX_{i,k} \in D_{i}, what the lowest possible local cost is, given the CPA [eq:aaai:localmin]. Agent A1A_{1} will return a CostMsg(Θ1\Theta_{1}) message with the mapping Θ1={𝚐→1,𝚢→0,𝚋→0}\Theta_{1} = \{\texttt{g} \to 1, \texttt{y} \to 0, \texttt{b} \to 0\} and for agent A2A_{2} this mapping will be Θ2={𝚐→0,𝚢→1,𝚋→0}\Theta_{2} = \{\texttt{g} \to 0, \texttt{y} \to 1, \texttt{b} \to 0 \}. For both A4A_{4} and A5A_{5} it will be Θ4=Θ5={𝚐→0,𝚢→0,𝚋→1}\Theta_{4} = \Theta_{5} = \{\texttt{g} \to 0, \texttt{y} \to 0, \texttt{b} \to 1\}, and agent A3A_{3} its own costs are Θ3={𝚐→1,𝚢→1,𝚋→0}\Theta_{3} = \{\texttt{g} \to 1, \texttt{y} \to 1, \texttt{b} \to 0\}. All cost maps will be received by A3A_{3}, which sums over the possible assignments and finds {𝚐→2,𝚢→2,𝚋→2}\{\texttt{g} \to 2, \texttt{y} \to 2, \texttt{b} \to 2\}. There are now three potential assignments leading to the same minimal cost. Since initially β=1\beta= 1, the choice is delayed until more information is available (because β<3\beta<3 and other neighbors are still either ACTIVE or IDLE). Agent A3A_{3} sends an UpdState(3{3}, HOLD) to its neighbors.

Since A1A_{1} and A2A_{2} are already DONE, they will not react to the new information. Agents A4A_{4} and A5A_{5} are now activated and after inquiring their neighbors, they gather a combined mapping Θj={𝚐→2,𝚢→2,𝚋→1}\Theta_{j} = \{\texttt{g} \to 2, \texttt{y} \to 2,\texttt{b} \to 1\}. They can both find a unique minimal solution, so they assign their value to Xj←𝚋X_{j} \leftarrow \texttt{b}. Agents A4A_{4} and A5A_{5} send a SetVal(j{j}, b) to spread the algorithm’s activity and their new value. Upon receiving this information the neighbors update their CPA accordingly. Immediately after, an UpdState(j{j}, DONE) message is sent, notifying all neighbors that they are now done.

Activity returns to A3A_{3}, who receives two UpdState(j{j}, DONE) messages. After the first message it will assume that another neighbor is still active and will run the algorithm again without increasing β\beta. This time, A3A_{3} will find assignment costs {𝚐→2,𝚢→2,𝚋→3}\{\texttt{g} \to 2, \texttt{y} \to 2, \texttt{b} \to 3\} (assuming that one of the neighbors is done, otherwise it would contain 𝚋→4\texttt{b} \to 4; this is a race condition). As there are two minimizers and the uniqueness bound β=1\beta= 1, A3A_{3} will go to the HOLD state. After the second UpdState(j{j}, DONE) message arrives, A3A_{3} knows that there are no more active neighbors, so it will increase its bound β←2\beta\leftarrow 2. Now it will find the cost of assignments to be {𝚐→2,𝚢→2,𝚋→4}\{\texttt{g} \to 2, \texttt{y} \to 2, \texttt{b} \to 4\} with two distinct minima; since the uniqueness bound is now 2, it will select a random minimizer out of the two.

3.3.3 CoCoA: Termination Guarantees

With the state-mechanism in place, one could run the risk of entering an endless loop. We have the following Proposition:

Proposition 3.1. The CoCoA algorithm will converge after a finite number of messages and function evaluations.

Proof. Assume a situation in which an agent AiA_{i} and all of its neighbors are in the HOLD or DONE state. At some point AiA_{i} receives an UpdState(j{j}, S) message and it will find that there are no more active neighbors, thus increases its β\beta by one. CoCoA will run again and either there will be a unique solution or not. If no solution is found, AiA_{i} will set its state to HOLD, we are again at an impasse, and the process will repeat. At some point however β=|Di|\beta= |D_{i}| since the domain is finite. At this point any assignment must satisfy 𝒰(Xi)≤β\mathcal{U}(X_{i}) \leq \beta, so a value will be picked, and an endless loop is avoided. ◻

3.3.4 CoCoA: Privacy

When solving ADCOPs, there is always the possibility of transmitting the full local constraint cost matrix to one agent’s neighbors. Sharing all constraint information between neighbors, and adding the received costs to the local costs, effectively converts any ADCOP into an equivalent symmetric DCOP. This strategy is also referred to as Private Events as Variables (Maheswaran et al. 2004), and the main motivation not to use this strategy is the loss of privacy. In literature there are four different types of privacy defined (Léauté and Faltings 2013): agent privacy, topology privacy, constraint privacy, and decision privacy. The max-sum algorithm is known to be very private (Tassa, Grinshpoun, and Zivan 2017), especially because of its unique bipartite approach, separating utility and function nodes. However, when we consider constraint privacy, we argue that CoCoA is at least as privacy-conserving as max-sum.

Proposition 3.2. CoCoA preserves at least as much privacy as max-sum.

Proof. The max-sum algorithm is known to be more privacy preserving than the local search algorithms ACLS and GCA-MGM (Zivan, Parash, and Naveh 2015). Only in two iterations entries from the cost matrices are exchanged between agents. In other iterations the shared values are derived from multiple entries as information spreads through the graph. CoCoA, on the other hand, shares cost matrix entries only once, i.e. before any agent has assigned a value and after that it is always derived from multiple entries. In CoCoA, for each assignment, the lowest total cost is sent taking into account the complete CPA (line 17 of Algorithm 1). As with max-sum, in every message to AiA_{i}, |Di||D_{i}| values are transmitted, however since CoCoA does not iterate, the number of exchanged messages is lower. ◻

3.4 CoCoA Performance: Experimental Results

CoCoA is tested and compared against state of the art DCOP solvers, being: DSA (Fitzpatrick and Meertens 2003) (variant C, with update probability, p=0.5p = 0.5), MGM-2 (Maheswaran, Pearce, and Tambe 2004) (with offer probability p=0.5p = 0.5), max-sum_ADVP (Zivan, Parash, and Naveh 2015) from hereon also referred to as simply max-sum, (switching graph direction after 100 iterations, value propagation after two switches, and using the constraint standard inner order), ACLS (with update probability p=0.5p = 0.5) and GCA-MGM (Grubshtein et al. 2010) (non-parametric). Also, we show the individual effects of the SSLA and the unique-first approach by showing the results for CoCoA with and without the unique-first (UF) strategy.

For all experiments 100 problems are generated (the type of problems will be described subsequently) and the presented results are the average over all problems. To compare the performance of CoCoA we look at the following performance metrics: (i) the cost of the final solution (S), (ii) the number of transmitted messages (M), (iii) the number of cost function evaluations (E), and (iv) running time of the algorithm (T). A cost function evaluation is defined as computing or looking up the local cost of one constraint, similar to Non-Concurrent Constraint Checks (NCCCs) (Meisels et al. 2002). These are not necessarily non-concurrent, but they do indicate a non-implementation specific measurement of computational effort. We keep track of the global cost function and when no better solutions are found for more than 100 iterations the solver is stopped. Afterwards we report the performance metrics at the moment where a solver was first within 1% of the best solution. This approach is similar to an anytime framework as described in (Zivan, Okamoto, and Peled 2014; Mahmud et al. 2019), but instead of keeping track of the best state at every agent, we maintain this information in the experiment script; this information is only used for evaluation.

The solvers are implemented in Java 1.7, and the experiments are set up in MATLAB 2015b, which is also used to post-process and present the result figures1. The experiments are carried out on a laptop with an Intel Core i7-3720 CPU 2.6 GHz and 8 GB RAM.

3.4.1 Graph Coloring

A common problem for benchmarking DCOP solvers is the graph coloring problem e.g. (Maheswaran, Pearce, and Tambe 2004; Modi et al. 2005; Rogers et al. 2011). As in the example run, the values of 𝒳\mathcal{X} represent the colors of nodes, and the solvers need to assign colors such that nodes on the ends of edges have different colors. In the first experiment every constraint violation will induce a cost of 1. In the experiment the number of colors |D|=3|D_{}| = 3, so the cost matrix for every constraint is 𝐂=𝐈3\mathbf{C}=\mathbf{I}_{3}. The graphs are generated by selecting n=500n= 500 random points in two-dimensional space using a Poisson point process, representing the variables, and the constraints are chosen as the edges of a Delaunay triangulation between those points—the average density of the graphs is 0.01.

3.4.1.1 Experiment Results

In Figure 3.2 the solution cost is plotted against the running time for several algorithms, while Table 3.3 shows the full set of metrics. CoCoA_UF finds a solution of near optimal cost in a single iteration, requiring less function evaluations than any other algorithm, and second least number of messages; therefore it is also the fastest algorithm. The result demonstrates that the unique-first approach definitely provides a benefit in terms of eventual solution cost, as CoCoA_UF finds a solution that is 20% better than CoCoA at the cost of some additional messages and cost function evaluations, almost as good as DSA, which finds the best.

In the experiment max-sum is left out since it is unable to converge to a solution. This is because there are |D||D_{}| “mirrored” solutions that perform equally well, and there is no local preference of one coloring over the other.

Figure 3.2: Graph coloring experiment: DSA finds the best solution, but CoCoA_UF finds a similar solution in less time.

Table 3.3: Graph coloring experiment results

Algorithm | I | S | M*^* | E*^* | T
CoCoA | N/A | 183 | 8.8 | 138 | 0.5
CoCoA_UF | N/A | 147 | 15.4 | 152 | 0.8
ACLS | 35 | 189 | 101.0 | 194 | 3.5
DSA | 200 | 129 | 28.3 | 1 177 | 18.9
GCA-MGM | 58 | 144 | 128.0 | 213 | 6.0
MGM-2 | 80 | 184 | 98.2 | 452 | 8.1

*=×103^* = \times 10^3

3.4.2 Semi-Randomized Asymmetric Problems

In the second experiment we generate semi-random asymmetric problems by creating scale-free graphs according to (Albert and Barabási 2002) with an initial graph of ten randomly connected nodes, and iteratively adding up to four nodes until n=200n= 200, resulting in graphs with an average density of 0.04. The variable domain size |Di|=10|D_{i}| = 10, and for every constraint an integer semi-random cost is generated for both sides of the constraints. A cost of zero is selected with a probability of p=0.35p = 0.35 and uniformly randomly chosen in the domain [1,100]\left[1,100\right] for the remainder. This setup recreates the experiment as described in (Grinshpoun et al. 2013Section 5.2). In this experiment the DSA and MGM-2 algorithms are taken into account, even though it is already known that they cannot solve asymmetric problems; they are used to demonstrate the fact that this problem is indeed an ADCOP.

3.4.2.1 Experiment Results

Figure 3.3: Semi-randomized asymmetric experiment: CoCoA finds a Pareto-optimal solution, but GCA-MGM eventually finds the best solution after more than 60 seconds.

Table 3.4: Semi-randomized asymmetric experiment results

Algorithm | S*^* | M*^* | E*^* | T
CoCoA | 29.3 | 4.8 | 1 595 | 0.3
CoCoA_UF | 27.4 | 6.9 | 1 334 | 0.3
ACLS | 26.6 | 153.1 | 1 296 | 5.0
DSA | 32.3 | 40.8 | 1 250 | 3.8
GCA-MGM | 22.3 | 1 349.2 | 5 397 | 59.8
MGM-2 | 35.1 | 91.8 | 3 287 | 11.5
Max-sum | 27.1 | 1 709.4 | 51 221 | 133.9

*=×103^* = \times 10^3

Figure 3.3 presents the solution costs of different algorithms as they converge to a solution. CoCoA and CoCoA_UF quickly converge to a good solution, more than 10 times faster than any other algorithm. The symmetric DCOP solvers DSA and MGM-2 fail to find a solution. The max-sum algorithm also converges to a reasonable solution, but only after more than two minutes (not visible in Figure 3.3). The GCA-MGM algorithm shows a “discovery” phase in the first 25 seconds, after which it finds a global optimum, which is better than any other algorithm finds. The added overhead of the GCA-MGM algorithm can clearly be seen in Table 3.4. The better solution is found by sending nearly 200 times the amount of messages, evaluating 4 times the number of cost functions and running 200 times longer than CoCoA_UF.

3.4.3 Sensor Planning

Figure 3.4: Sensor planning experiment: CoCoA finds the optimal solution and converges the fastest out of all evaluated algorithms.

Table 3.5: Sensor planning experiment results

Algorithm | S | M*^* | E*^* | T
CoCoA | 2 365 | 1.2 | 389 | 0.1
CoCoA_UF | 2 365 | 1.8 | 332 | 0.1
ACLS | 3 934 | 7.0 | 44 | 0.3
DSA | 3 332 | 13.1 | 427 | 1.3
GCA-MGM | 2 379 | 197.2 | 952 | 10.7
MGM-2 | 2 917 | 24.5 | 1 161 | 3.9
Max-sum | 1 246 306 | 12.0 | 1 300 | 0.9

*=×103^* = \times 10^3

The final experiment is motivated by an example in which a sensor network is used to monitor the cargo state of a shipping container. The sensors have to maintain a good quality estimation of the cargo such that they can either warn the cargo owner in case the shipping circumstances unexpectedly change, or provide a trace of the cargo state upon arrival. In this scenario the cargo estimation has to be optimized, but is constrained by limited battery life. The scenario is the adapted from Chapter 2, from which we use the outcome to model the effect of the communication frequency on the estimation quality and the battery lifetime. In this problem 𝒳\mathcal{X} are communication rates between sensors, and hard constraints make sure that the agents (nodes) will meet the minimum required battery lifetime. Asymmetric constraints between agents are used to model the effect that more shared information does not reduce the local estimation error, but it does improve the performance of neighboring nodes. The domains 𝒟\mathcal{D} are integer communication frequencies of [1,11]\left[1,11\right] Hz, and the networks are generated by connecting n=50n= 50 nodes, in randomly generated graphs with an average density of 0.17.

3.4.3.1 Experiment Results

The results are show in Figure 3.4 and Table 3.5. They show that CoCoA is not only capable of finding the best solution, but also does so in the least amount of time and using the fewest messages from all considered algorithms—only in terms of computational effort, ACLS is more efficient. However, ACLS is unable to find a better solution than the symmetric solvers DSA and MGM-2. This may contribute to its low evaluation count—it is simply considered as “converged” after a few evaluations.

3.5 Conclusions

In this chapter we studied the problem of coordinated decision-making in multi-agent systems. In order to reason about the configuration of an agent, taking into account the neighboring agents, we have proposed and investigated a new ADCOP solver: CoCoA. CoCoA is a non-iterative, semi-greedy strategy using SSLA to incorporate the effect a decision has on neighboring nodes. We compared its performance with state-of-the-art solvers by using (i) three-color graph coloring, (ii) randomized asymmetric problems and (iii) a sensor network use case problem.

We showed that CoCoA finds high quality solutions, with a similar overhead for symmetric problems, and a much smaller overhead for asymmetric problems, both in terms of communication and running time. The GCA-MGM algorithm finds better solutions for randomized asymmetric problems, but requires up to 200 times more messages, and over 4 times more cost function evaluations. In the sensor planning problems CoCoA finds better solutions, and does so faster than the benchmarks. When we look at performance of the algorithm with or without the unique-first approach, we can conclude that preferring unique solutions yields a clear advantage in terms of solution cost.

Because CoCoA requires no iterative approach, it can be used in applications where fast convergence is required, or when communication is a limiting factor. We have shown that for this reason CoCoA is very well suited to find assignments in sensor planning problems. CoCoA seems a promising method for collaborative decision-making, to find communication strategies that benefit everyone.

In recent studies, another extension of DCOPs was proposed: Functional DCOPs or F-DCOPs. In F-DCOPs the variable domains are continuous, and consequently the constraints must be expressed as functions, and cannot be written as tables (Hoang, Yokoo, and Rabinovich 2020; Choudhury, Mahmudand, and Khan 2019; Fransman et al. 2020). C-CoCoA (Sarker et al. 2020) is an extension of the CoCoA algorithm, which is capable of solving F-DCOPs, using the same strategies underlying CoCoA i.e. it uses a non-iterative one-step lookahead to asses the effects of local decision on neighboring nodes.

A downside of CoCoA is that it cannot recover from early choices, and there is a serious chance of simultaneous assignments in neighboring nodes which in the presence of hard constraints may lead to infeasible solutions. In the next chapters, these shortcomings will be addressed. First, in Chapter 4 an extension is presented that avoids simultaneous assignments, which will be utilized in a use case with hard constraints in wireless power transfer. Then, in Chapter 5 an extension is considered, where the best of both worlds is exploited; the fast convergence of CoCoA is complemented with high quality solutions, and possibility to improve on early choices, of other solvers.

For a replicability of results and figures, the source code of the implemented algorithms is available at https://github.com/coenvl/jSAM/tree/AAAI17, and of the experiment setups and visualization at https://github.com/coenvl/mSAM/tree/AAAI17.↩︎

4 Self-organizing Wireless Power Transfer

4.1 Introduction

In this chapter, an extension to the CoCoA algorithm (from the previous chapter) is introduced called CoCoA Controlled Activation (CoCoA_CA). As we concluded in the previous chapter, CoCoA is a good starting point for an algorithm driving self-organization, but might have difficulty dealing with hard constraints. The underlying problem is that the activation of the algorithm is likely to occur simultaneously in neighboring agents. When this happens, both agents make a decision based on the same information, but cannot take into account the assignment that other agent is making. In order to address this, an additional check is added to make sure simultaneous decisions cannot occur, and experiments are carried out to see the effect of this additional cycle.

A use case is presented in which a self-organizing system controls a network of Wireless Power Transfer (WPT) transmitters. These transmitters form a system which has a goal to provide electrical power to a group of receivers, by means of radio frequency (RF) waves. Such radio waves are safe for operation in an environment where humans are also present, provided that transmission levels are maintained. In this chapter we will propose a wireless charging protocol, built on top of the CoCoA_CA algorithm. Since for the WPT use case, it is crucial that safe transmission levels are maintained, hard constraints must be implied on the underlying problem (when represented as a DCOP). Therefore, we will need to make sure that hard constraints are never violated, justifying the use of the CoCoA_CA algorithm.

4.1.1 A Primer on Wireless Power Transfer Networks

Today’s ecosystem of the IoT is composed of millions of embedded devices that can monitor and control the physical world (Al-Fuqaha et al. 2015). These devices are equipped with several hardware components such as sensors, actuators, microcontrollers and transceivers, that still consume a considerable amount of power. Fortunately, the research efforts on electronic circuits have already decreased the power consumption of these hardware components to a few microwatts (Gollakota et al. 2014). This allows the provision of power wirelessly by means of harvesting the energy of RF waves (Mishra et al. 2015; Visser and Vullers 2013). As the efficiency of harvesting circuits will improve, in the future more devices can be powered wirelessly, using only RF energy without any external power source such as batteries.

The electromagnetic radiation (EMR) at a particular point can be modeled as a linear function of the received power (Dai et al. 2014a; He et al. 2013). Since, several energy transmitters can be active simultaneously to charge nearby receivers, it might be the case that the total EMR value at some particular points in the charging area—which have a contribution from all active transmitters—can exceed the limit defined by the RF exposure regulations (Q. Liu, Yıldırım, et al. 2016; Dai et al. 2014a). Therefore, a safe-charging WPTN must ensure that it does not create harmful electromagnetic radiation (Wu, Rappaport, and Collins 2015), as it is trying to minimize the charging time by increasing the power levels of the transmitters (Q. Liu, Yıldırım, et al. 2016).

For safe, sustainable and continuous operation, a wirelessly-powered IoT system requires several dedicated RF energy transmitters that can control their power level to charge nearby receivers collaboratively, forming a Wireless Power Transfer Network (WPTN) (Q. Liu, Golinński, et al. 2016; Galinina et al. 2018; Huang and Zhou 2015). The deployment of this conceptual network is an important issue for the fast provisioning of wireless energy. Since in such a network the amount and locations of receivers is continuously changing, it is especially important to make use of a power optimization strategy, that is fast and reliable. Therefore, using local information for decentralized decision-making seems an appropriate strategy, and hence self-organizing multi-agent systems, is a natural fit for this problem.

4.1.2 Problem Statement

The main challenge is the maximization of the total transmitted power by finding individual transmission power levels of the transmitters, while satisfying the safety constraints, which is even more difficult due to the dynamic charging environment. There are two requirements that need to be addressed:

Dealing with the dynamic environment New energy transmitters, as well as receivers, can be introduced to the charging system. This means that EMR values at some particular locations can exceed the threshold if these new transmitters start provisioning power. The optimization strategy needs to be able to include addition, removal or changing of its variables and constraints.

Dealing with model uncertainty Based on a transmitter output power, it is difficult to model and estimate exactly the received power, and in turn the EMR value, due to the environmental dynamics of the RF wave propagation. Therefore, the latest (local) information should always be taken into account, and an offline centralized charging algorithm is not feasible.

Apparently, self-adaptation or self-organization shall become a necessary property of a WPTN such that the charging algorithm should transfer the network into a safe state, when the safety constraints are violated. Unfortunately, we are unaware of a self-organizing and safe charging algorithm in the current literature that (i) allows energy transmitters to interact with the energy receivers and sensors locally in a dynamic environment; (ii) does not use a centralized entity to find sub-optimal power levels subject to safety regulations.

4.1.3 Contributions

In this chapter we propose a method based on DCOP solvers to find near-optimal solutions for the optimization problems without any centralized entity and by only using local interactions among the nodes. Accordingly, in this chapter, we introduce a new wireless charging system called TESSA (Transferring Energy Safely by Self-Adaptation). TESSA is based on a variation of the DCOP solver CoCoA proposed in Chapter 3, and is self-adaptive, in the sense that it runs an algorithm on the transmitter nodes that will find an optimal transmission power level. This not only keeps a WPTN near-optimal in terms of power transfer, but also safe with respect to EMR regulations. Within this context, we provide the following contributions to the state of the art:

We formulate a distributed constraint optimization problem where the energy transmitter devices maximize the total transmitted power to the receiver devices, i.e. minimize the charging time, while keeping the network safe in the EMR sense using measurements from the locally deployed sensors;

A variation on the CoCoA algorithm is proposed, called CoCoA_CA, that enables solving the distributed optimization problem, while making sure the EMR thresholds are never violated. This algorithm drives a self adaptive charging system, called TESSA. TESSA optimized the charging network to a safe state, even when perturbed by environmental dynamics such as new energy transmitters joining in the network;

We compare the CoCoA_CA algorithm with the existing DCOP solvers via simulations. Our results show that the existing algorithms are unable to find feasible solutions, whereas CoCoA_CA finds solutions near the theoretical optimal, reaching on average 85% of the maximum (optimal) solution, in terms of power transmission;

We show that our charging system based on DCOP solvers maintains safe EMR levels, without relying on a model for the RF propagation. Hence, it is capable of dealing with unexpected RF measurements, which a model-based centralized solution cannot.

4.2 Related Work

We provide a brief overview of the related work on wireless power transfer and distributed constraint optimization, which our work builds upon.

4.2.1 Wireless Power Transfer

The number of IoT nodes continues to grow exponentially (Shaikh, Zeadally, and Exposito 2015; Bertino et al. 2016). This exposes a problem of sustainable energy provision to such a mass of (battery-powered) IoT devices. Fortunately, the recent advancements in RF energy harvesting and low-power electronics, e.g.  (Gao et al. 2014), make it feasible to power ultra low-power microcontroller-based IoT devices wirelessly using electromagnetic energy (Smith 2013). Wireless power transfer revealed several optimization problems that gained considerable attention from the research community, e.g. the optimization of the harvested power (Krikidis 2014), energy outage (Huang and Lau 2014) and charging delay (Fu et al. 2013).

However, the electromagnetic safety issues provide additional constraints on the wirelessly supplied power. Specifically, since an EMR value that is above the limits of well-defined regulations (Kalialakis and Georgiadis 2014) is considered as a threat to human health (Non-Ionizing Radiation Protection (ICNIRP) 1998), it introduces an important constraint to the objective of aforementioned optimization problems.

To the best of our knowledge, there are only two recent studies (from the same authors) that target the optimal wireless power transfer incorporating the human health effects. A one-shot centralized solution that maximizes the total transmitted power subject to the safety constraints at each point on a predefined deployment area is presented in (Dai et al. 2014a)—in (Dai et al. 2014b), the same problem is handled in a distributed fashion. Unfortunately, these two studies have a fundamental drawback: they use deterministic models to estimate EMR. However, RF propagation is non-deterministic and modeling errors might lead to violate the safety constraints. Moreover, the distributed algorithm in (Dai et al. 2014b) is quite complex and composed of several phases. The algorithm employs a distributed redundant constraint reduction algorithm, splits the deployment area into small squares and employs linear programming (LP) by considering the local constraints inside each square. Therefore, it cannot be considered as a self-organizing solution since optimization is not performed by local interactions solely, rather than using the global information within each square.

The charging algorithm that we will introduce is not dependent on any RF propagation model since it uses direct measurements from the sensor nodes. Therefore, it always satisfies the safety constraints. Moreover, our algorithm is fully-distributed and self-organizing, based on the local interactions among the energy transmitters, receivers and sensors.

4.2.2 Distributed Constraint Optimization

DCOPs are a type of problems from the field of multi-agent systems where agents need to cooperatively assign a set of variables in order to optimize some cost function. We introduced the formalization and notation of DCOPs in Section 3.2. DCOP solvers can be divided into complete and incomplete solvers, which provide either the global optimal solution, or a near-optimal solution near the overall best, respectively. However, since the optimization problems are NP-hard (Modi 2003), optimal solvers are by definition exponentially slow for increasing problem sizes. Therefore, for the application for WPT, we are more interested in incomplete solvers that are not guaranteed to find the optimal solution, and find a good solution in a feasible time.

4.2.2.1 Iterative solvers

Most incomplete DCOP methods use an iterative approach and belong to the class of local search algorithms. This means that these solvers start with an initial variable assignment and iteratively search the local problem space for a solution that incrementally improves, until it converges to a local optimum. Some examples of solvers belonging to this class are the DSA (W. Zhang et al. 2005), MGM or MGM-2 (Maheswaran, Pearce, and Tambe 2004) algorithms. Solvers for problems with asymmetric constraints such as ACLS and GCA-MGM (Grinshpoun et al. 2013) or max-sum (Zivan, Parash, and Naveh 2015) are also considered iterative.

4.2.2.2 Non-iterative solvers

There exist some complete non-iterative solvers in the literature such as DPOP (Petcu and Faltings 2005a), ADOPT (Modi et al. 2005) or AFB (Gershman, Meisels, and Zivan 2009). However, since these complete solvers are very time-consuming, for the Wireless Power Transfer problem an incomplete solver is preferable. To the best of our knowledge there is only one non-iterative incomplete approach, which is offered by the CoCoA algorithm as introduced in Chapter 3.

The advantage of the non-iterative solvers is that they will immediately present their final solution. This means that if the solver is capable of finding a solution that satisfies the EMR constraints, it will immediately find this solution, thus never violating the EMR thresholds. This is in contrast to iterative solvers, that might initially violate the constraints, even if it may eventually find a solution that yields more transmitted power.

4.3 System Model: A Network of Energy Provision

We abstract a WPTN as a graph in the 2D plane, that has different types of nodes representing either energy transmitters (ETs), energy receivers (ERs) or sensor nodes. It is assumed that each ET node is equipped with an antenna that can emit RF waves to charge ER nodes inside its power transmission range wirelessly. Besides, each ER node is assumed to be equipped with an RF-harvester circuit that accumulates the harvested energy into the storage component. Moreover, each sensor nodes is assumed to be able to measure the EMR value at its specific location.

We further assume that each ET, ER and sensor node is equipped with a transceiver that allows communication with the other nodes inside their communication range. For the sake of simplicity, it is assumed that the power transmission range of the ET nodes are identical to their communication range, and ET, ER and sensor nodes are stationary during the optimization process.

4.3.1 ET Model

The set of ET nodes is denoted by T={T1,T2,…,Tt}T_{}=\{T_{1}, T_{2},\ldots, T_{t}\}, where tt represents the number of ETs. We denote the transmission power of TiT_{i} such that i∈{1,…,t}i \in \{1,\ldots,t\} by PiP_{i} and assume that each ET node can modify it by assigning values in the interval [Pmin,Pmax][P_{\min},P_{\max}]. The set of ER and sensor nodes with which TiT_{i} can communicate and transfer power, i.e. the set of neighbors of TiT_{i}, is denoted by ℳi\mathcal{M}_{i}.

4.3.2 ER Model

We denote the set of ER nodes by R={R1,R2,…,Rr}R_{}=\{R_{1}, R_{2},\ldots, R_{r}\}, where rr represents the number of ERs. Each Rj∈ℳiR_{j} \in \mathcal{M}_{i} such that j∈{1,…,r}j \in \{1,\ldots,r\} receives power from the ET node TiT_{i}. Following the model in (He et al. 2013Eq. (4)) which is based on Friis’ free space equation, the harvested power at RjR_{j} from TiT_{i} can be expressed as Pi→j=ηGiGjLp(λ4π(dij+β))2Pi,P_{i\rightarrow j} = \eta \frac{G_iG_j}{L_p}\left(\frac{\lambda}{4\pi (d_{ij}+\beta)}\right)^2P_{i}, where GiG_i and GjG_j are antenna gains of TiT_{i} and RjR_{j}, λ\lambda is the wavelength, LpL_p is the polarization loss, β\beta is a parameter to adjust the Friis’ free space equation for short distances, dijd_{ij} denotes the distance between TiT_{i} and RjR_{j} and η\eta represents the efficiency coefficient of the RF harvester. By introducing γ=GiGjLp(λ4π)2\gamma = \frac{G_iG_j}{L_p}\left(\frac{\lambda}{4\pi}\right)^2, we can write Pi→jP_{i\rightarrow j} in compact form as Pi→j=ηγ(dij+β)2Pi.P_{i\rightarrow j} = \eta \frac{\gamma}{(d_{ij}+\beta)^2}P_{i}.

In reality, the emitted energy waves from transmitters can combine at receivers either constructively or destructively, that might led to energy cancellation (Naderi, Nintanavongsa, and Chowdhury 2014). For the sake of simplicity, we consider only the case of constructive combination. In turn, we model the total harvested power at receiver RjR_{j} as the sum of individual received energy from the transmitters, which we denote by θj\theta_j as θj=∑i:Rj∈ℳiPi→j.\label{eq:harvested_power} \theta_j = \sum_{i:R_{j} \in \mathcal{M}_{i}}^{}P_{i\rightarrow j}.

4.3.3 Sensor Model

The set of sensor nodes is denoted by S={S1,S2,…,Ss}S_{}=\{S_{1}, S_{2}, \ldots,S_{s}\}, where ss represents the number of sensors. Each sensor SkS_{k} such that k∈{1,…,s}k \in \{1,\ldots,s\} is able to measure the EMR value at its specific location. We model the EMR value at SkS_{k} as a linear function of the total transmitted power as Ek=ρ∑i:Sk∈ℳiγ(dik+β)2Pi,\label{eq:sensor_emr} E_{k} = \rho \sum_{i: S_{k} \in \mathcal{M}_{i}} \frac{\gamma}{(d_{ik}+\beta)^2}P_{i}, where ρ\rho is a constant that captures the linear relationship between the EMR and received power, and dikd_{ik} denotes the distance between TiT_{i} and SkS_{k}.

4.4 Problem Description

We define the centralized linear programming problem. Define EMR threshold as α\alpha and let 𝒫=[P1,…,Pt]T\mathcal{P}=\left[P_{1},\ldots,P_{t}\right]^T. We formulate the optimization problem as max𝒫∑jθj,s.t.∀k:Ek≤α,Pmin1≤𝒫≤Pmax1,\label{eq:saso:problem:LP} \begin{split} \max_{\mathcal{P}}\quad & \sum_{j}^{}\theta_j, \\ \text{s.t.}\quad & \forall k: E_k \leq \alpha, \\ & P_{\min} \mathbf{1}\leq \mathcal{P}\leq P_{\max} \mathbf{1}, \\ \end{split} where 1\mathbf{1} denotes a vector with all components equal to 1.

4.4.1 Translation into a DCOP

In DCOPs problems are described as a tuple 𝒯=⟨𝒜,𝒳,𝒟,ℛ⟩\mathcal{T}= \langle \mathcal{A}, \mathcal{X}, \mathcal{D}, \mathcal{R}\rangle. We can formulate the wireless power transfer problem by stating that every transmitter in TT_{} is represented by an agent 𝒜={A1,A2,…,An}\mathcal{A}= \{A_{1}, A_{2}, \ldots, A_{n}\} and their corresponding transmission powers in PP_{} are the variables that are being optimized 𝒳={X1,X2,…,Xn}\mathcal{X}= \{X_{1}, X_{2}, \ldots, X_{n}\}. One of the main assumptions in DCOP theory is that all variables must have finite discrete domains 𝒟\mathcal{D}, which should contain every possible power level. This means that the interval [Pmin,Pmax][P_{\min},P_{\max}] has to be discretized to contain a finite set of possible values, yielding nn variable domains 𝒟={D1,D2,…,Dn}\mathcal{D}= \left\{D_{1},D_{2},\ldots,D_{n}\right\}. This discretization can follow a specific set of possible power values that the energy transmitter allows.

Finally, in a DCOP, ℛ\mathcal{R} is the set of constraints, which map the assignment of variables to a non-negative cost: C:Di1×Di2×…×Dik→ℝ≥0C{:~} D_{i_1} \times D_{i_2} \times \ldots \times D_{i_k} \to \mathbb{R}_{\geq 0}. In the WPT problem statement [eq:saso:problem:LP] there are two types of constraints. Firstly, we have the constraints that will maximize the amount of energy transmitted. These constraints represent the ER nodes RR_{} with a constraint cost function such that CRj=−θj.\label{eq:powercost} C_{R_{j}}=-\theta_j. Note that we model maximization of transmitted energy, as the minimization of the negative energy. Secondly, there is the set of sensors SS_{} that are modeled using a threshold constraint. This constraint aims to make sure that the EMR safety threshold should not be exceeded. This is modelled as CSk={0,if Ek<α,τ,otherwise,\label{eq:sensorcost} C_{S_{k}}= \begin{cases} 0, & \text{if } E_k < \alpha, \\ \tau, & \text{otherwise}, \end{cases} where a hard constraint can be simulated by choosing τ=∞\tau = \infty as described in (Boerkoel and Durfee 2013), or simply a very high value such that θj≪τ\theta_j \ll \tau. Hence, the full set of constraints ℛ\mathcal{R} can be defined as the combined set of both receiver and sensor constraints ℛ={CR1,CR2,…,CRr,CS1,CS2,…,CSs}\mathcal{R}= \left\{C_{R_{1}}, C_{R_{2}}, \ldots, C_{R_{r}}, C_{S_{1}}, C_{S_{2}}, \ldots, C_{S_{s}}\right\} such that the minimization function will maximize the transmitted power, while minimizing the number of sensors where the EMR threshold is violated. The DCOP minimization function is defined simply as arg min𝒳∑ℛ.\underset{\mathcal{X}}{\text{arg min}} \sum{\mathcal{R}}.

4.5 TESSA: A Safe Wireless Charging System

Having presented the system model of wireless power transfer we consider in this chapter, we are ready to present our charging system. We first present the high-level charging protocol that governs the charging requests of the energy receiver devices. Then, we present the extension of CoCoA denoted as CoCoA_CA, which is triggered by TESSA.

4.5.1 The Main Charging Protocol

Algorithm 2: Charging Protocol executed by Transmitter TiT_{i}

1: | 𝖱i←∅\mathsf{R}_{{i}} \leftarrow \emptyset {Vector of charge requests for transmitter ii}
| Upon receive Charge from Rj∈ℳiR_{j} \in \mathcal{M}_{i}
2: | 𝖱i←𝖱i∪{Rj}\mathsf{R}_{{i}} \leftarrow \mathsf{R}_{{i}} \cup \{R_{j}\} {Add new request from receiver jj}
3: | Reset CoCoA_CA {Execute CoCoA_CA optimizer}
| Upon receive EndCharge from Rj∈ℳiR_{j} \in \mathcal{M}_{i}
4: | 𝖱i←𝖱i\{Rj}\mathsf{R}_{{i}} \leftarrow \mathsf{R}_{{i}} \setminus \{R_{j}\} {Remove request from receiver jj}
5: | if 𝖱i=∅\mathsf{R}_{{i}} = \emptyset then
6: |     Turn off charger TiT_{i}
7: | end if
8: | Reset CoCoA_CA {Execute CoCoA_CA optimizer}

The main charging protocol, executed by each transmitter TiT_{i} in the wireless power transfer network, is presented in Algorithm 2. The objective of this protocol is to trigger the CoCoA_CA algorithm, presented in Algorithm 3 and discussed in Section 4.5.3, that will determine the sub-optimal power levels for the transmitters. Initially, the power transmitter can be turned off and waiting for a receiver inside its neighborhood ℳi\mathcal{M}_{i} to send a Charge message. The transmitter will add the corresponding receiver to its requests list 𝖱i\mathsf{R}_{{i}} and reset the CoCoA_CA algorithm to recalculate the optimal power levels (Lines 1–3). Similarly, when a EndCharge message is received, the corresponding receiver is removed from the requests list, the transmitter is turned off if the requests list is empty and CoCoA_CA algorithm is restarted (Lines 5–10).

Figure 4.1: Illustrative example of TESSA execution. Transmitters T1T_{1} and T2T_{2} are currently charging the receiver R1R_{1} subject to the constraint on the sensor S1S_{1}. The receiver R2R_{2} sends a charging request to transmitters T2T_{2} and T3T_{3} that forces T3T_{3}, T2T_{2}, and in turn T1T_{1}, to run the CoCoA_CA optimizer again with also considering the constraints on the sensor S2S_{2}.

The rationale behind resetting and in turn restarting the actual DCOP solver CoCoA_CA is to force the network to adapt to the new state. As an example, consider Figure 4.1: transmitters T1T_{1} and T2T_{2} are currently charging receiver R1R_{1}, and receiver R2R_{2} sends a charging request to transmitters T2T_{2} and T3T_{3}. Since the sensor S1S_{1} is already in the neighborhood of T3T_{3} and there is a new sensor S2S_{2} that will be solely affected by the power transmission of T3T_{3}, the EMR constraints on these sensors will affect not only the power level of T3T_{3} but the current power level of T2T_{2} and in turn T1T_{1}. Therefore, if T3T_{3} starts/resets CoCoA_CA, the neighboring transmitter T2T_{2} should be informed. In turn, that will lead T2T_{2} to inform T1T_{1} so that all transmitters re-calculate the optimal power levels.

4.5.2 CoCoA and Race Conditions

The CoCoA algorithm is introduced in Chapter 3. By itself, it already has some properties to avoid race conditions, i.e. situations in which two agents simultaneously make a decision on a variable assignment. However, they are not fully effective, since two agents may become simultaneously activated from different neighbors. Also, CoCoA is designed under the assumption that there are only binary constraints in the problem graph; when applied to higher order constraints, race conditions are more likely to occur and may involve more than two agents.

Figure 4.2: Race condition problem of CoCoA in the wireless power transfer context. In the initial state (top), since S1S_{1} is measuring 0 W, both transmitters decide on a high value eventually exceeding the example EMR threshold of 0.18 W (bottom). E1E_1 is computed according to [eq:sensor_emr] where S1∈ℳ1S_{1}\in\mathcal{M}_{1} and S1∈ℳ2S_{1}\in\mathcal{M}_{2}.

If race conditions would occur in the WPT scenario, this means that two (or more) transmitters simultaneously decide on a power level. The situation may occur as shown in Figure 4.2, where initially two transmitters (T1T_{1} and T2T_{2}) are simultaneously actively running the CoCoA algorithm. As they both know that a shared sensor (S1S_{1}) is not exceeding the EMR threshold, they may decide both to increase their power level. Not taking into account the assignment of the neighbor, it is possible for the two agents to assign two values that actually would violate the EMR constraint.

It is very difficult to avoid race conditions from occurring in a multi-agent system. However, since CoCoA already provides a mechanism to disseminate the current state of the algorithm, we can detect if one has occurred. In the following section we introduce the extension of CoCoA: CoCoA_CA, where race conditions are recognized, and concurrent assignments avoided.

Algorithm 3: CoCoA_CA Algorithm

| Algorithm start on AiA_{i}:
1: | Assign ϕi←𝙰𝙲𝚃𝙸𝚅𝙴\phi_{i} \leftarrow \texttt{ACTIVE}{} and inform neighbors
2: | Send request to neighbors for cost maps
3: | Wait for all responses
4: | if number of ACTIVE higher ranked neighbors >0> 0 then
5: |     Go to line 2
6: | end if
7: | Find minimizing assignments for XiX_{i}
8: | if number of minimizer ≤β\leq \beta{} or number of idle/active neighbors is 0 then
9: |     Assign XiX_{i} and ϕi←𝙳𝙾𝙽𝙴\phi_{i} \leftarrow \texttt{DONE}{}; send to all neighbors
10: | else
11: |     Assign ϕi←𝙷𝙾𝙻𝙳\phi_{i} \leftarrow \texttt{HOLD}{} and send to all neighbors
12: | end if
| Upon receiving cost inquiry message at AjA_{j}:
13: | for all Xi,k∈DiX_{i,k} \in D_{i} do
14: |     Calculate costs for Xi,k∩θr∩EsX_{i,k} \cap \theta_{r} \cap E_{s}
15: | end for
16: | Reply AiA_{i} with all costs
| Upon receiving new state ϕi\phi_{i} from Ai∈ℳjA_{i} \in \mathcal{M}_{j} on AjA_{j}:
17: | Store neighbor’s state ϕi\phi_{i}
18: | if ϕi\phi_{i} is HOLD and ϕj=𝙷𝙾𝙻𝙳\phi_{j} = \texttt{HOLD}{} and number of idle/active neighbors is 0 then
19: |     Increment uniqueness bound β\beta and repeat algorithm
20: | else if ϕi\phi_{i} is DONE and ϕj\phi_{j} is HOLD then
21: |     Repeat algorithm
22: | end if
23: | Upon receiving Reset on AiA_{i}:
24: | if ϕj≠𝙸𝙳𝙻𝙴\phi_{j} \neq \texttt{IDLE}{} then
25: |     Assign ϕj←𝙸𝙳𝙻𝙴\phi_{j} \leftarrow \texttt{IDLE}{}
26: |     Forward Reset to all neighbors
27: | end if

4.5.3 Solving CoCoA Race Condition Issue: CoCoA_CA

In Algorithm 3 we present the pseudocode of the CoCoA_CA algorithm. Note that in the algorithm we use ϕi\phi_{i} to denote the state of AiA_{i}, which initially is IDLE, but can be set to ACTIVE, HOLD or DONE. Also, the uniqueness bound β\beta{} is initially set to 1. CoCoA_CA starts out the same way as CoCoA does by inquiring the neighbors the costs of local assignments. Then in lines 4–6 the algorithm checks whether any neighboring agents are also currently running, and if there are—it will go back in the algorithm to the point where it will gather information anew. However, since this current agent itself is also running, we would introduce a deadlock here, where two simultaneously activated neighbors would stay in this cycle ad infinitum. In order to break this potential deadlock we introduce this notion of ranking.

At line 4, we check the number of higher ranked neighbors. In principle any ranking could be used, as long as all involved agents agree on the ranking. In our implementation we use the alphabetical ranking of the identifier of the variable, but any other rankings, such as the MAC addresses of the agents may be used as well. Even a random number selected at the time of this impasse would serve, as long as there is always one highest ranked agent. Only the highest ranked agent may finish the variable assignment, and the other agent(s) will have to restart the algorithm. By doing so, we make sure that no two agents are deciding on an assignment simultaneously.

Between line 7 and 12, where the algorithm assigns a variable based on the neighbors’ cost messages, the logic is the same as for CoCoA. All received costs are added, and the minimizing value is selected if the uniqueness of the minimizer is less or equal than β\beta{}.

When a message is received inquiring about the assignment costs (lines 12–16), nodes update their state based on the received value assignments and gather information from the receivers based on either their actual measurements or estimations based on the theoretical energy harvesting model as per [eq:harvested_power], and from the sensors by requesting their measured power level. By using the actual measured power, not the model predicted amount, we can make sure that the EMR thresholds are always satisfied. Using this information we can compute the local cost with [eq:powercost] and [eq:sensorcost] in line 14.

For handling the state update message from neighbors (lines 17–22) the same logic is applied as in the original CoCoA algorithm. Whenever a HOLD state is received, the algorithm checks if the uniqueness bound β\beta needs to be updated, or it will repeat the algorithm if the agent itself is in the HOLD state and a neighbor informs us that it is finished.

Finally, an additional message was added to reset the algorithm. At line 23 we specify that if a Reset message is received, it will update the local state to IDLE and forward the message to the neighboring agents, if the state was not already reset.

4.6 Experiments

We performed four experiments to evaluate the performance of the different methods in the WPT scenario. For all experiments we generate 200 problem instances and let all methods solve the same problem instance. For the DCOP solvers we had to discretize the potential power levels into |D|=20|D_{}| = 20 levels linearly spaced in [Pmin,Pmax]\left[P_{\min}, P_{\max}\right] where Pmin=0P_{\min} = 0 W and Pmax=10P_{\max} = 10 W. We set the power transmission variables arbitrarily to the values γ=β=100\gamma = \beta = 100 and η=ρ=1\eta = \rho = 1. The EMR threshold was set to α=0.018\alpha= 0.018 W, and the threshold violation cost τ=109\tau = 10^9 W. For all experiments we define the total solution cost as the sum of all constraint costs as per [eq:powercost] and [eq:sensorcost], i.e. negative the amount of total power consumption plus τ\tau times the number of sensors where the EMR threshold is violated.

To generate the problem graph we selected the position of the tt transmitters using a Poisson point process in 2D space. Subsequently, the rr receiver and ss sensor locations are selected using the same method, and their locations are then scaled such that they span the same area. We determine the average distance of the third-nearest neighbor in Euclidean space and define that any sensor or receiver within this distance, is a neighbor of the transmitter, and hence will receive energy. Using this method we can generate a seemingly natural distribution of nodes with some variation in the number of neighbors that a transmitter has. An example of such a generated graph is shown in Figure 4.3, with t=70t= 70, r=60r= 60 and s=50s= 50.

Figure 4.3: An example randomized graph as generated using the proposed methods for the simulation experiments with t=70t= 70, r=60r= 60 and s=50s= 50. There are receivers and sensors with 1 up to 4 transmitters visible.

All experiments were performed in simulation on a laptop with an Intel Core i7-6600U at 2.6 GHz and 16 GB of RAM.1

4.6.1 Comparing Solvers

In the first experiment we compare the performance of various DCOP solvers with the centralized solver. For this experiment we generated problems with t=100t= 100, r=75r= 75 and s=50s= 50. We compare the results of the DCOP solvers CoCoA_CA, ACLS, DSA, max-sum and GCA-MGM introduced in Section 3.2.1 with a centralized LP solver. As a stopping criterion for the iterative solvers we keep track of the reported solution cost. When it has not dropped for 100 iterations we stop the simulation, and report the metrics at the moment at which the solution was first within 1% of best found solutions.

Figure 4.4: Various iterative algorithms fail to find a solution that satisfy the receiver constraints. CoCoA_CA however is capable of finding a valid solution, similar to the centrally computed optimum.

Table 4.1: Numerical results of the DCOP solvers. Colored costs indicate hard constraints being violated—red numbers are consistent constraint violations, and orange numbers indicate incidental violations.

Algorithm | I | S | M*^* | E*^* | T
CoCoA_CA | N/A | -1.932 | 1.7 | 299 | 0.3
ACLS | 27 | 33×10933\times 10^{9} | 1.0 | 74 | 0.3
DSA | 16 | 28×10928\times 10^{9} | 3.1 | 54 | 0.2
GCA-MGM | 117 | 13×10913\times 10^{9} | 34.6 | 210 | 1.1
Max-sum | 49 | 4×1074\times 10^{7} | 30.0 | 312302 | 321.7

*=×103^* = \times 10^3

From the results in Figure 4.4 we can see that from all DCOP solvers, only CoCoA_CA is consistently capable of finding solutions that satisfy the EMR threshold constraints. Averaged over 200 experiments, it found a solution that transmits 1.93 W in 0.33 s compared to 2.15 W in 0.03 s for the centralized LP solver. Of course because it is constrained in the exact values of the power levels, its final solution cost is somewhat worse. The max-sum algorithm did perform relatively well, but took very long to solve the problem, hence was left out from Figure 4.4.

In Table 4.3 the numeric results of the experiment are shown. These correspond to the results in Figure 4.4, but also show the communication overhead and the number of iterations for the iterative solvers. For every algorithm the amount of iterations (I), the final solution cost (S), the number of transmitted message (M) and the time to solve (T) in seconds. The max-sum algorithm violated constraints 3.5% of the time (probably because in those situations max-sum failed to converge, as it may not converge on cyclic graphs), but if it does not, the mean cost is –2.067 W, which is slightly better than CoCoA’s mean result. Only in one instance out of the 200 experiments did GCA-MGM find a solution that did not violate the EMR constraints, whereas DSA and ACLS never did.

4.6.2 Scalability

In the second experiment we investigate the performance of the CoCoA_CA algorithm under varying problem sizes. Fixing all other parameters of the problem we generate instances with increasingly more transmitters (varying between 4 and 1024), and 0.8 times as many receivers and 0.6 times as many sensors.

Figure 4.5: CoCoA_CA has the capability of solving even larger graphs, and the distance to the global optimum is linearly dependent on the graph size.

In Figure 4.5 the solution cost is shown for CoCoA_CA and the LP solver for increasingly large problems. As can be seen, CoCoA_CA performance is only linearly worse than the optimal solution for the problem size. On average the solution by CoCoA_CA yields 85% the amount of power compared with the optimal solution found by the LP solver.

4.6.3 Performance Under Model Error

In the third experiment we validate our hypothesis that using a DCOP approach will keep performing well, even under unpredictable amounts of energy transmitted. In the TESSA charging system, the sensor nodes communicate to the ETs, their actual measurements of the EMR values which do not always perfectly follow the model as proposed in Section 4.3; for example because of quantization effects. Similarly, the ET nodes can either use (i) the amount of measured harvested power based on the measurements by the ERs or (ii) the predicted total harvested power based on the theoretical model represented by in [eq:harvested_power].

In all previous experiments we assumed that (i) our theoretical model in Section 4.3 perfectly represents the amount of transmitted energy and (ii) both sensors and receivers perform measurements reflected by [eq:harvested_power] and  [eq:sensor_emr]. In order to explore the effect of the measurements on the performance of our system, we introduce an error in the model on how much energy is received by the receivers and the sensors. i.e. for any combination of transmitter ii and receiver jj the amount of harvested energy is Pi→j′=ϵηγ(dij+β)2Pi=ϵPi→j,P_{i\rightarrow j}' = \epsilon \eta \frac{\gamma}{(d_{ij}+\beta)^2}P_{i} = \epsilon P_{i \rightarrow j}, and similarly the amount of EMR measured by a sensor kk is Ek′=ϵρ∑i:Sk∈ℳiγ(dik+β)2Pi=ϵEk,E_k' = \epsilon \rho \sum_{i:S_{k} \in \mathcal{M}_{i}}^{} \frac{\gamma}{(d_{ik}+\beta)^2}P_{i} = \epsilon E_k, where ϵ\epsilon is a random noise multiplier from the normal distribution ϵ∼𝒩(1,σ2)\epsilon \sim \mathcal{N}\left(1, \sigma^2\right): white noise added to the amount of transmitted power from the original model.

Figure 4.6: The total transmitted power of all receivers, shows that noise in the model is not of large influence to the solution quality of the DCOP solver. The line in the graph shows the theoretical optimum without model noise.

In Figure 4.6 the results are shown for the CoCoA_CA algorithm as it solves different problems with an increasing amount of noise, compared to the centralized LP solver. We observe that our solver performs well by continuously satisfying the EMR constraints. The centralized LP solver makes its assignments based on the predetermined energy harvesting and EMR model and cannot take into account the actual measurements. Obviously, it is possible to extend the LP solution where sensor measurements are sent to the central solver, removing any model noise. However, that can not longer be considered a centralized solution.

In a purely centralized solution, because of modeling and measurement errors, in practical scenarios it is impossible to estimate the actual harvested power and in turn the EMR values (Q. Liu, Yıldırım, et al. 2016). If we apply the solution found by the LP solver in the noisy model, we find that in all instances except where σ=0\sigma = 0, some sensor constraints were violated, leading to invalid solutions. The solutions of the LP solver without model noise are shown in Figure 4.6 as a lower bound.

4.6.4 Dynamic Environment

In the final experiment we investigate the performance of the TESSA charging system under network dynamics. In this experiment we generate a network with 10 transmitters, 8 receivers and 6 sensors. We run the TESSA charging system, and randomly add or remove agents. Specifically in every second there is a 5% chance that the network will change, and if it does, then half of the times a transmitter is added, and half the time a randomly selected transmitter is removed from the WPTN. The CoCoA_CA algorithm is reset every second.

Figure 4.7: We can see that TESSA finds safe solutions, no EMR threshold violations of τ\tau are seen, that are near the optimal solutions found by the LP solver. Upward arrows (green) indicate a random transmitter was added to the environment, and downward triangles (red) indicate the removal of a transmitter.

Figure 4.8: Example of tracking the amount of individual received powers for all ER in the dynamic experiment, showing the minimum, average and maximum amount of received power for all ERs.

Figure 4.9: The EMR is logged for every sensor in the dynamic environment experiment. Here we show the EMR threshold at 0.018 W (red dashed line), together with the minimum, average and maximum measured EMR of all sensors.

In Figure 4.7 the total amount of transmitter power is presented for both TESSA, and for the centralized LP solver that calculates the optimal power levels. Observe that when a transmitter is removed from or added to the charging system which is currently charging receivers, TESSA disseminates a Reset message (see Algorithm 2) to start the optimization process again. Therefore, the charging network reacts to this disturbance by re-calculating the optimal power levels of the whole transmitters with respect to the EMR safety constraints. Eventually, all transmitters will start transmitting energy according to the new power levels that comply with the new safety constraints in accordance with the new structure of the network.

In Figure 4.8 the amount of received power is shown over time. The minimum, average and maximum amount of power is shown, for the full set of ERs. It is obvious that there is a some spread between ERs, due to the random placement of both receivers and sensors. Receivers that are near one or more sensors, obviously cannot be charged, due to the exposure in the sensors. The EMR levels of the sensors in the dynamic placement experiment are shown in Figure 4.9; again here we show the minimum, average and maximum exposure of all sensors. From this Figure we can determine that even for the most exposed sensor, the maximum EMR threshold is never violated. However, due to the formalization of the optimization problem [eq:saso:problem:LP], the amount of received radiation of the sensors is maximal, but always less than the EMR threshold.

This network adaptivity is almost impossible to achieve with the centralized LP solver. The reason is that, for each transmitter removal or addition, the whole state of the network—including transmitter power levels, the positions of the receivers and the sensors—should be collected and sent to the central entity that calculates the optimal LP solution. What is more, the results of these calculations should be distributed back to the corresponding transmitters so that they update their power levels. Thanks to TESSA and the CoCoA_CA solver, adaptivity is achieved by only the local interactions among the agents in our system.

4.7 Conclusions

In this chapter we introduced an extension to the CoCoA algorithm that limits the activation of neighboring agents, to avoid simultaneous decisions. This enables the algorithm (called CoCoA_CA) to deal with hard constraints, and also find assignments with even lower solution costs. This new algorithm is the driving force of a new self-organizing wireless power charging system TESSA, for safe wireless power transfer, to ensure that electromagnetic radiation levels never exceed safety guidelines. We formalized the safe wireless charging problem as a DCOP so that any DCOP solver can be used to solve this problem. We compared CoCoA_CA with existing solvers and justified that it is capable of consistently finding solutions that maintain safe levels of EMR. Then, we presented experiments that showed the TESSA charging system is self-adaptive in the sense that it reacts to the network dynamics and always transfers the network to an EMR-safe state, while ensuring a high total transmitted power.

In our experiments we show that CoCoA_CA consistently finds solutions that maintain the EMR thresholds, whereas other DCOP solvers can not. The amount of transferred power was on average 85% of the amount of power transferred in the theoretical optimal conditions, independent of the problem size. The losses can be partially explained by the fact that the solver is incomplete, so better solutions may be possible. Also, because the DCOP solver can only choose a power level from a finite set, whereas in the optimal setting any power level between the minimum and the maximum can be selected. Unfortunately we were unable to find performance guarantees with respect to the optimal solution, other than our empirical results. We also showed that our method was able to find a solution that satisfies the EMR threshold, by communicating measurements from sensors to transmitters. This makes the method more robust, by not relying on a (potentially unreliable) RF model.

We did not perform any experiments involving hardware implementations, but this would be the reasonable next step in providing safe wireless charging solutions. This will yield valuable information about how well the methods perform with realistic disturbances and practical problems.

In this chapter CoCoA_CA definitely outperformed DCOP solvers from the current literature, but in earlier experiments (e.g. Chapter 3) we have already seen that in other classes of problems this is not always the case. In the next chapter, we will introduce hybrid DCOPs in which we can combine the benefits of different DCOP solvers. This could benefit TESSA, for instance, by initially finding a proper solution using CoCoA_CA, and then improving it with other solvers—something that CoCoA by itself cannot.

For reproducibility of the results all code for the algorithms (Java) is available from https://github.com/coenvl/jSAM/tree/SASO2017, and experimental setups and visualization (MATLAB) from https://github.com/coenvl/mSAM/tree/SASO2017.↩︎

5 Hybrid DCOPs

5.1 Introduction

In this chapter we continue our work for finding an algorithm that is capable of driving self-organization through DCOPs. In Chapter 3 we introduced CoCoA, which differs from existing state-of-the-art DCOP solvers, in the sense that it does not require multiple iterations, or cycles of negotiations and assignments. Instead, it uses a single step lookahead (SSLA) approach to find a reasonable assignment, and then finishes its execution. We have already shown that this offers very good performance in many use cases, and already provided an extension CoCoA_CA in Chapter 4 that enables it to deal with hard constraints. But CoCoA is non-iterative, which (by definition) makes it impossible to recover from early mistakes. Therefore, the issue of recovery from early mistakes is addressed in this chapter. We will generalize the SSLA approach, as well as study the effect of continuing local search with other algorithms, after a SSLA solver has found an initial assignment.

As we have already shown in earlier chapters, Distributed Constraint Optimization Problems (DCOP) are a method for formalizing and solving problems that have a distributed nature, and in which multiple cooperating agents control discrete variables in order to optimize a common problem. Moreover, a special kind of DCOP can be formulated where agents having a shared constraint may assign different costs for a value assignment; these problems are called Asymmetric DCOP (ADCOP) (Grinshpoun et al. 2013). In ADCOPs the aspect of cooperation and distributed decision-making is even more important, because (in contrast to DCOP) in ADCOP an assignment leading to a local improvement may deteriorate the global performance. This makes ADCOPs especially important to consider when designing a self-organizing multi-agent system.

In Section 3.2.1 we introduced a variety of DCOP solves, and stated that we can classify them as either complete or incomplete solvers. In this chapter we introduce a new class of incomplete (A)DCOP solvers, that combine features of different solvers and combine them into hybrid solvers. Specifically, we show that we can use different initialization methods for existing (iterative, local search) (A)DCOP algorithms, which has a profound impact on their overall performance. In order to achieve this, we use different initialization methods that are not iterative in approach, and are hence very fast in determining a solution. Empirically we show that compared to existing state-of-the-art DCOP solvers, we can reduce algorithm running times and improve the solution quality.

5.2 Problem Statement

For the definition and formal problem statement that are addressed in DCOPs, we refer the reader to Section 3.2. There exist already DCOP-solving algorithms, with varying ranges of efficiency in terms of solution quality, computational effort, communication overhead or convergence speed. Selecting the right algorithm for solving the problem at hand depends on the topology, type of constraints and the problem scale; often this is a matter of trial-and-error. Often there are multiple solvers that outperform other solvers on at least one of the performance criteria, and there is no single best strategy. Therefore, we foresee the need to combine different solving algorithms into one solution, and to study which techniques are best put together.

5.3 A New Class of DCOP Solvers: Hybrid Solvers

By combining different algorithms into a hybrid solver, we aim to get a method which takes “the best of both worlds.” Particularly, we propose to improve the performance of existing local search algorithms by modifying the initialization methods to find the initial value assignment. In the field of Constraint Satisfaction Problems, which is closely related to DCOPs, the approach of using an initialization and repairing it is well known, and can yield great benefits (Minton et al. 1992). From the fields of evolutionary algorithms (Rahnamayan, Tizhoosh, and Salama 2007), clustering (Cao, Liang, and Jiang 2009), neural networks (Yam and Chow 2000; Dolezel, Skrabanek, and Gago 2016), meta-learning (Feurer, Springenberg, and Hutter 2015) and other machine learning techniques we know that initialization methods can have a great effect on the performance of an algorithm. However, to the best of our knowledge, there has been little to no work on the effects of different initialization methods for (A)DCOPs. In this chapter we will study the effect different initialization methods may have on the performance of (existing) DCOP algorithms in the form of hybrid DCOP solvers.

We define a hybrid DCOP solver as a solver which executes sequentially other (existing) DCOP solvers.

5.3.1 Motivation for a Hybrid DCOP Solver

Most (if not all) local search DCOP algorithms use an initial random assignment for all the variables, which will be iteratively improved upon. Instead, an initial assignment can be computed by a non-iterative DCOP algorithm, such as a simple greedy algorithm, or a more elaborate greedy algorithm such as the one introduced in (Leeuwen and Pawełczak 2017). Since these methods will assign a value only once, and then terminate, they quickly provide a good initialization assignment from which one can start another DCOP method.

We hypothesize that the combination of different initialization methods for iterative algorithms in DCOP solution search, will be beneficial because of two effects:

Solution quality improvement over initial assignment: most probably a simple initialization method will find a sub-optimal solution, and many local search algorithms will be able to improve it. Algorithms that are known to provide monotonically decreasing solution costs (any algorithm that uses a coordinated change approach, e.g. MGM-2, ACLS, GCA-MGM) are guaranteed to find better (or equal) solutions compared with the initial value assignment; and

Increased convergence speed for local search algorithms: DCOP algorithms that use local search will most likely converge faster when a good solution is used for initial DCOP value assignment. This will lead to a shorter total running time for algorithms that are initialized with a better assignment.

5.4 Initialization of DCOP Solvers: Classification

In our experiments we combine different initialization methods with existing local search algorithms which we shall also refer to as iterative methods. Since the aim of this study is to improve the solution quality and convergence speed of solvers, we do not take into account complete solvers. To understand why only certain combination of DCOP solvers improves the solution, we need first to classify (i) initialization methods, and (ii) types of DCOP iterative solvers.

5.4.1 DCOP Classification: Initialization Methods

The initialization methods of DCOP algorithms can be classified into the following categories.

Random A de facto standard method for all DCOP solvers. It does not take into account any constraints and starts with the random variable assignment.

kk Step Look-ahead: We define a look-ahead initialization algorithm as the one in which one randomly chosen initial node is triggered first, and only after it has chosen a value it will activate its neighbors. When choosing a value, it takes into consideration the effect on all of its neighbors that are reachable within kk steps (edges or hops). Three special cases of kk step look-ahead are already known:

Zero Step Look-ahead (ZSLA): A zero step look-ahead algorithm (k=0k=0) is the one in which an agent optimizes only for the constraints it is directly involved in. Such algorithms are also referred to as greedy, breadth-first algorithms. This is essentially an asynchronous version of the DSA algorithm (W. Zhang et al. 2005) with p=1p=1;

Single Step Look-ahead (SSLA): A single-step-look-ahead algorithm (k=1k=1) is defined as one in which an agent optimizes not only for the constraints it is involved in, but also the constraints its one-hop neighbors are in. One such algorithm is the CoCoA algorithm and its variants CoCoA_UF introduced in Chapter 3 and CoCoA_CA introduced in Chapter 4;

Max Step Look-ahead (MSLA): If kk is equal to the height of the graph’s minimal spanning tree, and the algorithm would be started at the root of the spanning tree, the algorithm becomes a complete algorithm, and is in fact equivalent to DPOP (Petcu and Faltings 2005a). Strictly this method should not be considered a initialization strategy, since it is already a complete method.

5.4.2 DCOP Classification: Existing Iterative Methods

Classifying iterative methods used in DCOP solvers we can divide them into two main groups.

Symmetric DCOP Solvers: Solvers that only take into account symmetric constraints, which assume costs are the same for all agents involved. These include DSA (W. Zhang et al. 2005), MGM and MGM-2 (Maheswaran, Pearce, and Tambe 2004) and generalized DBA (Okamoto, Zivan, and Nahon 2016);

Asymmetric DCOP Solvers: Solvers that also take into account asymmetric constraints; here costs may be different for the involved agents. Examples of such solvers include GCA-MGM (Grubshtein et al. 2010), and ACLS (Grinshpoun et al. 2013) with its new version ACLS-UB (which is also a novel contribution of this work and described in Section 5.4.3).

Remark 5.1. We are naturally aware of another popular DCOP solver: the max-sum algorithm (Farinelli et al. 2008) or any one of its variants. However, max-sum is unable to utilize the benefit of initializing, as it tries to approximate the global utility of any value, and uses this to determine the best variable assignment. There are extensions of max-sum that are able to build upon an initial assignment by using value propagation (Zivan and Peled 2012). In a recent paper (Z. Chen, Deng, and Wu 2017) the effect of initialization was studied in variant called max-sum_ADSSVP. The authors find that the timing, and approach to initialization has a great effect on the performance, both in terms of solution quality and convergence speed. For our evaluation however, we leave max-sum out of the comparison, and refer to max-sum_ADSSVP to provide a complete overview of different hybrid algorithms.

5.4.3 Novel Iterative DCOP Solver: ACLS-UB

In addition to existing DCOP algorithms listed above we introduce a variant of the ACLS, denoted as unbiased (ACLS-UB).

In the original ACLS algorithm (Grinshpoun et al. 2013), at every iteration an agent chooses a variable assignment that would lower its local costs and proposes it as a new value to its neighbors. Neighbors respond with the effect on their side, after which the proposition which has the best effect on the regional cost function is selected. In the ACLS-UB algorithm a value assignment is proposed from all possible values, instead from the subset that improves its local state. The ACLS-UB algorithm is described using pseudo code in Algorithm 4.

ACLS-UB works by iteratively proposing a random value from its domain DiD_{i}, and sends that value to its neighbors. The neighbors respond by sending the effect of the assignment on their local costs, taking into account all known value assignments. When these local effects are received by the initial agent, it sums over all received effects, and assigns the proposed value with probability pp only if it will reduce the current local cost.

Algorithm 4: ACLS-UB Algorithm

| On agent ii (AiA_{i}) when activated
1: | Xi←chooseRandomValue()X_{i} \leftarrow \text{chooseRandomValue()}
2: | while (no termination condition is met) do
3: |     send XiX_{i} to all neighboring agents ∀Aj∈ℳi\forall A_{j} \in \mathcal{M}_{i}
4: |     υ←chooseRandomValue()\upsilon\leftarrow \text{chooseRandomValue()}
5: |     send υ\upsilon to ∀Aj∈ℳi\forall A_{j} \in \mathcal{M}_{i}
6: |     wait for incoming constraint cost δj\delta_{j} from AjA_{j}
7: |     Δi←∑jj∈ℳiδj\Delta_{i} \leftarrow \sum_{j}^{j \in \mathcal{M}_{i}}{\delta{j}}
8: |     if Δi<\Delta_{i} < current cost and random[0,1][0,1] <p< p then
9: |         assign Xi←υX_{i} \leftarrow \upsilon
10: |     end if
11: | end while
| On AjA_{j} when receiving υ\upsilon from AiA_{i}
12: | send constraint cost δj(Xj∩υ)\delta_{j}(X_{j} \cap \upsilon)

5.4.3.1 Relation of ACLS-UB to Other Solvers

The main difference between ACLS and ACLS-UB is in line 4 of Algorithm 4 where any random value is picked from the domain. In the long run, the effect of this pick is that the effect of all values from the domain are used to retrieve the induced effect on the neighbors’ local cost.

Intuitively ACLS-UB works very similar to CoCoA (Leeuwen and Pawełczak 2017; Leeuwen, Yıldırım, and Pawełczak 2017), with the major difference that CoCoA operates in one single iteration instead of iteratively trying different values. Another difference is that in ACLS-UB the neighbors will send back the value of the constraint cost, whereas CoCoA will send back the lowest induced cost for any assignment in conjunction with the proposed value and the CPA. This extra look-ahead is not efficient in ACLS-UB, since the next-hop neighbors will in fact already have an assignment, and the lowest cost will be too optimistic. Note that the unique-first approach of CoCoA is not required in ACLS-UB, as it can easily recover from any earlier suboptimal assignments in later iterations, whereas CoCoA cannot.

5.5 Hybrid DCOP Solvers: Introduction and Initial Results

In order to understand whether there is any benefit from hybrid solvers, we performed the following experiments1. For any problem, we initiate 200 problem instances which are initialized by three methods: random, ZSLA (i.e. greedy) and SSLA (i.e. CoCoA) and subsequently solved by other DCOP solvers (depending on the experiment). We report the average result of all problems. We assume a solver has converged when no better solutions have been found for more than 100 iterations, and define the moment of “convergence” as the first iteration in which the solution was within 1% of the minimal solution. In this way we can compare the convergence speed of different algorithms, and do not have to specify the number of iterations beforehand, in a way similar to the any-time solution as proposed in (Zivan, Okamoto, and Peled 2014).

As performance metrics we will score solvers on the following metrics:

The number of iterations required to converge, denoted as I;

Final cost of the solution when converged, denoted as S;

Number of transmitted messages during the run, denoted as M;

Number of constraint evaluations, denoted as E; and

Running time until convergence, denoted as T in seconds.

The constraint evaluations are indicative of the computational complexity and can also be referred to as Non-Concurrent Constraint Checks (NCCCs) (Meisels et al. 2002).

5.5.1 Experiment Results

Figure 5.1: In a three-color graph coloring experiment, when using an SSLA for initialization, the MGM-2 algorithm improves both speed and solution quality.

Table 5.1: Graph coloring experiment results

Algorithm | I | S | M*^* | E*^* | T
Random_DSA | 157 | 49 | 10.4 | 362.9 | 3.5
ZSLA_DSA | 164 | 49 | 10.7 | 381.6 | 3.7
SSLA_DSA | 115 | 47 | 14.5 | 381.3 | 3.1
Random_MGM-2 | 55 | 72 | 26.3 | 120.2 | 1.7
ZSLA_MGM-2 | 42 | 71 | 21.0 | 94.4 | 1.3
SSLA_MGM-2 | 7 | 54 | 12.2 | 121.0 | 0.7

*=×103^* = \times 10^3

5.5.1.1 Experiment 1: Symmetric DCOP

We use a (symmetric) graph-coloring problem with three colors, which have to be assigned to 200 variables. The constraints between the variables are chosen as the nodes were connected via a Delaunay triangulation, when the variables are points chosen randomly on a two-dimensional plane. The results of MGM-2 (p=0.5p=0.5) is shown in Figure 5.1, of which the numeric results are shown in Table 5.2 together with DSA (variant C, with p=0.5p=0.5).

5.5.1.2 Experiment 2: Asymmetric DCOP

An asymmetric problem is chosen where the constraints are created using a scale-free graph generation method (Albert and Barabási 2002), and are assigned semi-random asymmetric costs such that there is a high probability that a conflict of interests occurs. This problem is created specifically to benchmark asymmetric problems, and is described in more detail in (Grinshpoun et al. 2013Section 5.2). The result of the ACLS-UB (p=0.5p=0.5) algorithm is shown in Figure 5.2, and the results of all algorithms is presented in Table 5.3.

Figure 5.2: In a semi-random experiment (Section 5.5.1, Experiment 2), when using an SSLA for initialization, the ACLS-UB algorithm shows faster convergence to a better solution.

Table 5.2: Semi-randomized asymmetric experiment results

Algorithm | I | S*^* | M*^* | E*^* | T
Random_ACLS | 95 | 26.4 | 151 | 1 321 | 4.3
ZSLA_ACLS | 75 | 26.1 | 121 | 995 | 3.5
SSLA_ACLS | 48 | 24.2 | 107 | 10 571 | 4.9
Random_ACLS-UB | 333 | 24.7 | 531 | 5 747 | 14.8
ZSLA_ACLS-UB | 299 | 24.1 | 477 | 5 164 | 13.3
SSLA_ACLS-UB | 207 | 23.5 | 358 | 12 963 | 11.9
Random_GCA-MGM | 1 154 | 21.7 | 1 389 | 5 557 | 55.1
ZSLA_GCA-MGM | 1 022 | 21.6 | 1 232 | 4 935 | 48.8
SSLA_GCA-MGM | 781 | 22.0 | 970 | 13 599 | 40.0

*=×103^* = \times 10^3

5.5.1.3 Hybrid Solvers—Discussion of Initial Results

Based on the results from the first two experiments, we see that local search DCOP solvers using initialization methods other than random, reduced the required number of iterations before they converged, their execution time and communication overhead, but surprisingly also found a final solution with a lower cost. The only two exceptions (marked in bold in Table 5.2 and 5.3) are (i) when using the SSLA with DSA, in which case the messages of the SSLA increases the very low communication overhead of DSA, and (ii) when using an SSLA with ACLS, in which case the added run time of the SSLA increases the convergence time. The speed performance gain can be easily explained: a better initialization will reduce the amount of variable “tweaking” needed. However, how come the final solution is also lower and solution result dependent on the initialization method? In the following sections we will investigate this using three hypotheses to explain this phenomenon:

Hypothesis 1: A lower initial solution will always lead to a lower final solution;

Hypothesis 2: Using initialization methods other than random increases the explored portion of the solution space;

Hypothesis 3: The initialization method itself finds a starting point in the search space, from which a lower local minimum is reachable.

Let us experimentally verify these three hypotheses in detail.

5.5.2 Hypothesis 1: Solution Cost Correlation

The SSLA algorithm finds a lower initial cost than the ZSLA initializer, which in turn finds a lower cost than a random assignment. Hence, the first hypothesis is that a lower initial costs will (on average) lead to lower final costs. The initial state is known to be of great influence on the final solution, and a correlation between the initial cost and the final cost could explain why ZSLA or SSLA initialization methods lead to better final solutions.

To test this hypothesis we performed an experiment by repeatedly invoking the algorithms on the exact same problem setup, but with different random initializations. We gather information on the cost at initialization and of the eventual outcome. In Figure 5.3 we show the minimum, average, and maximum results of the algorithms solving 200 instantiations (the same problems for every algorithm) of three color graph coloring problems with a Delaunay graph of size n=100n=100. For this small experiment we only compare the DSA algorithm instantiated with a randomized approach with an algorithm that uses CoCoA_CA for initialization.

Figure 5.3: Starting the DSA algorithm from a different starting point will lead to a different outcome. This graph shows the minimum, average and maximum solution costs during the experiments.

From this experiment we see that for some iterations we do find a solution with the random strategy which is as good as the SSLA-initialized solution, however on average the final solution is worse. The spread of the initial and the final solution corresponds with the statistical spread of the random assignments, and some random initialization lead to better final solutions than others. If we look at the correlation between the initial cost and the final cost of the individual runs, then we find that there is no correlation between the cost of the initial random assignment and the final minimal cost. The Pearson correlation coefficient between the solution cost at the beginning and the end is 0.15. With these results we reject hypothesis 1.

5.5.3 Hypothesis 2: Increased Solution Space Exploration

A DCOP problem is generally a matter of solution space exploration. The solvers that are capable of effectively searching a larger portion of the solution space, will reasonably find a better final solution than solvers that cannot. Since local search algorithms search only a small fraction of the search space, the increase in search space exploration by a SSLA may be of large influence. Put differently, a better overview of the trends in the solution space may lead to insights as to where the best optimum lies. If we can show that the solvers using SSLA explore a larger part of the solution space than randomly initialized solvers, this may explain why they find solutions with the lower final cost.

To verify this, we construct an experiment in which we captured the CPA every time a constraint check is performed, so that we can store every explored value assignment. We did observe that SSLA searches a slightly larger portion of the solution space than ZSLA, which in turn searches a larger part of the solution space than random. However, the SSLA algorithm sometimes searches a smaller part of the solution space, largely because its successor algorithm converges so quickly. Therefore, with these results we reject hypothesis 2 as well, also because the differences are so marginally small that they cannot explain the significant effect on the results.

5.5.4 Hypothesis 3: Selection of Starting Point

The initial assignment determines the area of the solution space that is reachable through local search. It is possible that SSLA is capable of finding initial assignments that have relatively good local minima. To explain what we mean by this, let us sketch the following example.

Definition 5.1 (Bridge edge). A bridge edge is defined as an edge that, when removed from the graph, the graph will no longer be connected.

Suppose we have a graph with high modularity, meaning it consists of clusters of densely connected nodes, which are connected through relatively low number of bridge edges. The nodes on these bridges could initially induce a high performance penalty; and it may be impossible for a local search algorithm to escape from these expensive assignments because of the many low cost constraints around it on the surrounding nodes.

Figure 5.4: An example graph in which two dense clusters of nodes are connected by a single bridge.

As a minimal example suppose we have a three color graph coloring problem with a graph as shown in Figure 5.4. As we see node 0 and 10 have a constraint with many other nodes, and are connected to one another. If through some unfortunate random assignment, they are both given the same initial color (for example red) and the surrounding nodes are mostly other colors, then we expect that no local search algorithm will change that initial assigned color. This expectation is confirmed through a series of experiments in which we use the graph as depicted in Figure 5.4, letting the algorithms solve the graph-coloring problem. In one set of the experiments, the agents are hardwired to initialize with an assignment in which X0=X10X_{0} = X_{10}, and ∀i≠10Xi≠X0\forall_{i \neq 10}{X_{i} \neq X_{0}}. As we can see in Figure 5.5 for that subset, the local search algorithm is unable to find a solution in which this constraint is resolved. We also see, and in fact can guarantee that an SSLA algorithm will never assign the same color to endpoint vertices of a bridge, and will thus lead to better solutions.

Figure 5.5: The results of the GCA-MGM algorithm trying to solve the graph coloring problem in graph from Figure 5.4, with various initialization strategies. The “unfortunate” strategy is hardwired to get a conflict on the bridge.

Proposition 5.1. A SSLA will never assign the same color to the endpoints of a bridge.

Proof. (Sketch) When an SSLA starts, any random agent is activated first. If either bridge endpoint is selected first, then logically they will not be activated simultaneously. If any other node is selected, then this node will execute the algorithm and select a random initial assignment. After that it activates all of its neighbors, which will execute the algorithm, until at some iteration the first bridge endpoint is selected. At this moment the other endpoint cannot be activated, or the edge would not have been a true bridge.

Because the algorithm is active in one bridge endpoint, but never in both at the same time, one must assign a value before the other. Moreover, when an endpoint of the bridge eventually has to assign a value, no nodes from the other component can be assigned a value yet, because the bridge is the only connecting edge. Therefore, when the second bridge endpoint is activated it will only have the first endpoint as a constraining value, and will thus always pick a different value. ◻

Although this exact order of events will not hold for pseudo-bridges that connect clusters within a graph, there will be an ordering in which the nodes will be activated, as long as the detour path between the vertices on the pseudo-bridge is longer than three. In many graphs with high modularity, the values of nodes in the bridging constraints will therefore be chosen with low costs, and the coloring within the clusters can simply be permuted. Therefore, the local search algorithms that continue from these solutions are generally of higher quality, than those from random initial assignments.

If this final hypothesis is true, then we expect some different results in the performance of different types of graphs, especially for various densities. We would expect the benefit of an SSLA to decrease with problem graphs of higher densities, since in these graphs bridges or pseudo-bridges occur less frequently.

5.6 Graph Density

In our final experiment we use once more the graph coloring problem with a domain size |D|=3|D_{}| = 3, and instantiate randomly connected graphs with n=200n=200 with nine varying densities between 0.01 and 0.3. We generate 50 graphs of every density, let the different solver combinations (initialization and iteration) solve the same graphs, and report the average performance of all instances. The convergence criteria were identical to the experiment described in Section 5.5.

Figure 5.6: The solution cost versus the time of the MGM-2 algorithm when solving random graphs of different densities shows the impact of initialization methods. Up to a density of 0.1 there is a clear improvement on the solution cost.

In Figure 5.6 we show the averaged results for the MGM-2 solver, when solving the graphs with different densities. We can indeed conclude that for graphs with a low to medium density (up to 0.1), there is a benefit using SSLA initialization for the final solution cost. The increase in convergence speed deteriorates much faster, since the complexity of the SSLA is exponential with the node degree, and this increases with graph density. Note, the time the SSLA initialization takes is shown as the starting point of the line. For other local search algorithms (DSA, ACLS, GCA-MGM), similar results were found.

5.7 Conclusions

In this chapter we introduced a new class of hybrid algorithms which combine the benefits of different DCOP algorithms. Particularly, we studied the effect of different initialization strategies on the performance of different DCOP algorithms. We found that using the combination of non-iterative SSLA algorithms with iterative local search algorithms, not only combines the fast convergence of the SSLA with the eventual better solution quality of the iterative approach, but that using another initialization improves the quality of the final solution.

Two possible hypotheses that could have explained these observations were proposed and rejected: (i) a correlation between the initial cost and the final solution cost does not exist, hence the effects are not from finding any initialization with a low cost, and (ii) somewhere in the complete solution space is the optimal solution, but using SSLA does not significantly increase the searched solution space. Instead, we hypothesize that using an SSLA (such as CoCoA and CoCoA_CA) selects an initialization that is in a region of the solution space that has a lower local minimum than the local minimum from a random starting point in the solution space. Furthermore, we propose that this is caused by a reduction of conflicting values assigned on bridge vertices. In our final experiment we show that the effect is most abundant on low density graphs, in which (pseudo-)bridges are more present, and the solution cost of the search space is less homogeneous. Not only did we determine in what situations an SSLA is effective, we also gained some insight into why an SSLA performs the way it does.

Our hybrid approach seems well suited for applications in which the problem graphs are not too dense (i.e. up to a density of 0.1), and where both convergence speed and solution cost are required. In fact, we may use it as a general strategy for initial value assignment instead of using random values in problems with low graph densities.

With this chapter, we conclude the work on CoCoA and using DCOPs as a coordination mechanism for collective decision-making. With the addition of hybrid solvers, we have a strategy for effecting self-organization, with a minimal communication and computational overhead using non-iterative SSLA, combined with an appropriate (depending on the type of problem) iterative DCOP solver. However, not all problems can be cast as a DCOP (efficiently). In the next chapter we present a use case for self-organization in the energy domain. Even though such a problem can and has been formulated as a DCOP, the resulting problem graph would be fully connected (density of 1), and hence the solution would not scale well (Fioretto et al. 2017). Instead, we will look at a different decision-making strategy for achieving self-organization based on a decentralized market mechanism.

For reproducibility and validation of our results, all (Java) code for the algorithms is available at https://github.com/coenvl/jSAM/tree/OptMAS18, and for the experimental setups (MATLAB) at https://github.com/coenvl/mSAM/tree/OptMAS18.↩︎

6 Self-organizing Smart Grid Planning

6.1 Introduction

In this chapter we propose a method to realize self-organizing planning in the energy domain. Specifically, we define an agent-based approach for planning the power consumption or production program for a smart grid of connected households.

Previously, in Chapter 3 and Chapter 4, we introduced some methods to coordinate decision-making using DCOPs. In such a solution all agents that are participating in the system need to coordinate their decisions with all agents that they affect. i.e. with all agents they share a constraint with. We have also shown in Chapter 5 that the performance of (Hybrid) DCOP solvers drastically deteriorate with increasing problem graph densities, which confirms what was found in other studies (Kumar, Petcu, and Faltings 2008; Fioretto et al. 2017; Z. Chen et al. 2018; Fioretto, Dovier, and Pontelli 2019). In this chapter, instead of using DCOP as a decision-making formalism for driving self-organization, a market-based strategy is proposed for cooperatively finding solutions that are feasible for all involved agents. A hierarchical multi-agent based approach is proposed, that uses local pricing to incentivize device controlling agents to schedule their usage in order to follow an agreed upon target profile and mitigate congestion. As we remarked in Chapter 1, not all agents in a self-organizing multi-agent systems need to be peers. In this chapter a hierarchy tree is used where at the top a “market operator” gathers information from all agents, and makes sure the common constraint is satisfied. Intermediate agents make sure the physical grid constraints are respected, and device agents at the bottom represent any end-user constraints or preferences. The resulting algorithm is not as re-usable as the solution presented in earlier chapters, but is tailored to the problem at hand: finding a feasible dispatch in the power grid.

Three trends set a challenge for future power grids. Firstly, the transition towards sustainable energy sources leads to more renewable energy, but also to a larger fraction of unpredictable and intermittent production. Secondly, the electrification of various systems such as transport (electric vehicles), heating (heat pumps), and in general an increase of electricity-consuming devices leads to a huge growth of power consumption. And thirdly, the distribution of energy generation leads to a very different pattern in the load of the power transmission grid, than it was designed for.

The control of a vast number of small power units, both consuming and producing, is extremely difficult to do completely top-down, so a centralized control strategy cannot be used (Kok and Widergren 2016). At the same time the power infrastructure is aging, and was not built for the emerging pattern of distributed prosumers (Gemine, Ernst, and Cornélusse 2017). This is why we need self-organizing control algorithms to schedule the use of electric devices while taking into account constraints of the power distribution infrastructure. This aids distribution system operators (DSO) and transport system operators (TSO) to maintain power balance and make sure there is no congestion, i.e. the grid capacity is not overloaded.

Table 6.1: Notations and parameters used in this chapter

Symbol | Description | Typical value | Unit
𝐀\mathbf{A} | topology matrix of child relations |  |
α\alpha | forecast accuracy | 0.90.9 |
𝑏\mathit{b} | vector of congestion thresholds | [2,3,…,3.5]×104[2,3,\ldots,3.5]\times10^4 | W
bib_i | congestion threshold of ii | 3×1043\times10^4 | W
𝒞i\mathcal{C}_i | constraint function of ii |  |
𝒞iZ\mathcal{C}^{\text{Z}}_i | constraint function of ii of type Z*^* |  |
γi\gamma_i | PV operation cost of ii | 0.20.2 |
𝑒i\mathit{e}_i | 1×T1\times T vector of energy of ii | [0.0,1.1,…,−0.3]×103[0.0, 1.1, \ldots, -0.3]\times10^3 | Wh
eite_{it} | energy of ii at tt | 200200 | Wh
eimine^\text{min}_i | minimum energy of ii | 0.00.0 | Wh
eimaxe^\text{max}_i | maximum energy of ii | 2×1032\times10^3 | Wh
𝛜\mathbf{\epsilon} | 1×T1\times T vector of errors | [0,11,…,−225][0,11,\ldots,-225] | W
ϵmax\epsilon^{\text{max}} | upper bound on the error | 10−310^{-3} | W
ηi\eta_i | storage efficiency of ii | 0.90.9 |
𝚯\mathbf{\Theta} | target power of the cluster | [1.9,−1,…,2.6]×104[1.9, -1, \ldots, 2.6]\times10^4 | W
ii | an agent index | 0,1,…,n0,1,\ldots,n |
JiJ_i | cost function of ii |  |
JiZJ^{\text{Z}}_i | cost of ii of type Z*^* |  |
λi\lambda_i | storage leakage of ii | 360†360^\dagger | W
ℳi\mathcal{M}_i | set of children of ii |  |
𝒩\mathcal{N} | set of all agents |  |
𝛒\mathbf{\rho} | 1×T1\times T vector of prices | [0.5,0.3,…,0.8][0.5, 0.3, \ldots, 0.8] |
TT | time horizon | 2424 |
tt | power time unit (PTU) index | 0,1,…,T0,1,\ldots,T |
τ\tau | duration of a PTU | 11 | h
𝑥i\mathit{x}_i | 1×T1\times T vector of scheduled powers of ii | [1.1,−0.5,…,0.4]×103[1.1, -0.5, \ldots, 0.4]\times10^3 | W
𝑥‾\bar{\mathit{x}} | 1×T1\times T vector of aggregated powers of child nodes | [24.0,−18,…,8.7]×103[24.0, -18, \ldots, 8.7]\times10^3 | W
𝑥′i\mathit{x}'_i | 1×T1\times T vector of expected powers of ii | [1.0,−0.4,…,0.8]×103[1.0, -0.4, \ldots, 0.8]\times10^3 | W
𝑥̂\hat{\mathit{x}} | 1×T1\times T vector of average historic powers | [0.8,0.6,…,−0.5]×103[0.8, 0.6, \ldots, -0.5]\times10^3 | W
xitx_{it} | scheduled power of ii at tt | −1.7×103-1.7\times10^{3} | W
ximinx^\text{min}_i | minimum power for ii | −2×103-2\times10^3 | W
ximaxx^\text{max}_i | maximum power for ii | 4×1034\times10^3 | W
ψi\psi_i | heat pump coefficient of performance (COP) of ii | 4.04.0 |

Note that powers are indicated from the grid perspective. That means positive powers indicate power going from the grid to the device, and negative powers are from the device back to the grid.

*^* Z indicates a type of agent, which can either be MO for market operator, CO for congestion, LOAD for a static load agent, PV for an agent with photovoltaic solar panels, or ST for a storage agent.

†^\dagger 360 W is chosen as an example thermal leakage of a house, which can be considered as an energy storage vessel.

6.2 Problem Statement

The problem at hand is a variation of the economic power dispatch problem (Ross and Kim 1980; Abido 2003), where the operation of a set of generators is optimized, such that power is provided to consumers in the most cost-effective manner. Traditionally this problem would include controllable generators (power generation plants), constraining transmission resources (transformers, stations, cables), and end-consumers having a static load. Currently, with distributed energy resources, and demand response—the possibility to control the load of consumers using flexibility of smart devices—the problem changes significantly.

A formal definition of the problem is as follows:

min𝑥∑i∈𝒩Ji(𝑥i),s.t.∑i∈𝒩𝑥i=𝚯,𝐀𝑥≤𝑏,ximin≤𝑥i≤ximax,∀i∈𝒩,𝒞i(𝑥i)=0,∀i∈𝒩,\begin{aligned} \label{eq:lprh:optim} \min_{\mathit{x}}\quad & \sum_{i\in \mathcal{N}} {J_i(\mathit{x}{}_i)}, \\ \text{s.t.}\quad & \sum_{i\in \mathcal{N}} {\mathit{x}_i} = \mathbf{\Theta}, \\ & \mathbf{A}\mathit{x}\leq \mathit{b}, \\ & x^\text{min}_i\leq \mathit{x}_i\leq x^\text{max}_i, & \forall i\in \mathcal{N}, \\ & \mathcal{C}_i(\mathit{x}_i) = 0, & \forall i\in \mathcal{N}, \end{aligned} with all parameters defined in Table 6.1, the objective function as defined in [eq:lprh:optim] is the same as for the traditional economic dispatch, which can be summarized as: to find a set of electrical powers 𝑥i\mathit{x}_i for every device i∈𝒩i\in \mathcal{N} in the grid, that minimizes the sum of all costs Ji(𝑥i)J_i(\mathit{x}_i). In the original dispatch problem defined, 𝒩\mathcal{N} defines only the producers. However, in our problem formulation [eq:lprh:optim] 𝒩\mathcal{N} denotes the full set of devices in the grid, including producers and consumers. This means that contrarily to the traditional economic dispatch problem, not only the generators are controllable, but also the flexible loads of end consumers.

Note that the costs in [eq:lprh:mincost] do not necessarily refer to the financial cost of a dispatch. Rather, this generic model only optimizes some social welfare, which defines a desirable outcome for all participants involved. Depending on the situation at hand, one could minimize the amount of greenhouse gasses emitted, or maximize the amount of renewable energy used. However, for the rest of this chapter the costs are defined as the energy losses of the devices. By minimizing the amount of energy losses we attempt to find a dispatch that is both economic and sustainable. Similarly, in this chapter when we refer to the price of energy, this does not necessarily refer to a financial price with a real currency, instead we will refer to a more abstract concept of the price of energy, which is used simply as a steering signal.

Let us discuss the constraints of [eq:lprh:optim], i.e. ([eq:lprh:constraint:target]–[eq:lprh:constraint:agent]). The constraint [eq:lprh:constraint:target] states that the sum of all powers in the system has to meet a specific target 𝚯\mathbf{\Theta}. In a balanced (island) grid this target has to be zero for every PTU, but in a connected grid this target is the contracted load with the transmission operator. Put differently, 𝚯\mathbf{\Theta} is the net power input of the grid to the rest of the world.

Constraint [eq:lprh:constraint:grid] defines the limitations of the physical power grid; a topology matrix AA specifies which device is connected to which grid components, and bb is the rating of those components—the maximum amount of power that it can safely transmit.

Constraints [eq:lprh:constraint:power] and [eq:lprh:constraint:agent] represent the constraints of the devices in the grid. Specifically, constraint [eq:lprh:constraint:power] states that a device cannot produce or consume more power than it physically can, which is represented by lower and upper bound, ximinx^\text{min}_i and ximaxx^\text{max}_i, respectively. However, [eq:lprh:constraint:agent] also takes into account another private constraint 𝒞\mathcal{C}. We refer to this constraint as private, as it only concerns the state of a single device, and may concern information that should not be shared with other parties. E.g. an end-user should not need to share its intent to run his or her washing machine with its neighbors. This constraint differs per device, and specifies device limitations such as a battery that cannot hold more than a certain amount of energy, and cannot discharge when already empty. Flexible loads also may have constraints considering the time at which they can turn on or off based on the consumer’s settings. We will elaborate on these constraints, as well as the cost functions of the device agents in Section 6.3.2.

6.2.1 Related Work

In existing studies, different strategies are used for energy management. Four different main categories are defined in (Kok and Widergren 2016) based on whether there is a distributed aspect of decision-making and whether there is one- or two-way communication. One of the strategies defined in (Kok and Widergren 2016) uses Transactive Control, where distributed systems decide locally on their device management, using two-way communication in a market-based control scheme. The authors compare this approach with traditional top-down switching, price-reaction and centralized optimization strategies and show that transactive control is capable of using the full flexibility potential of the smart grid devices, while maintaining the end-user privacy. This claim is consistent with earlier studies (Ygge and Akkermans 1999; Akkermans, Schreinemakers, and Kok 2004) that have shown that using a market-based control in a multi-agent system can provide equally optimal results as a centrally optimized system, under certain conditions.

Multi-agent based methods are already getting attention in the smart grid domain due to many desirable properties: robustness, user-friendliness, attack resistance and scalability (Pipattanasomporn, Feroze, and Rahman 2009; Colson and Nehrir 2013). The economic dispatch problem is very well suited to be represented using multi-agent systems (Cai, Nga, and Mitra 2012). There are many studies that use a multi-agent based approach to model and solve the problem, such as the two-way message passing agents using consensus algorithms to find an allocation that is optimal (Hu et al. 2018). Other methods use a completely decentralized method involving reinforcement (W. Liu et al. 2018), utility maximization (Li, Chen, and Low 2011) or model predictive control (Velasquez et al. 2019).

In (Warrington, Mariéthoz, and Morari 2011), a strategy is proposed to schedule the power consumption and production of generators and loads based on a method called Negotiated Predictive Dispatch. In this approach wind and conventional generators, as well as static and flexible loads, are controlled on the transmission level. Agents propose power schedules, which are aggregated by a central market operator, which then updates a price program using gradient descent, meaning the price of congested PTUs increase, and that of underused PTUs decrease. In doing so the authors show that they are able to balance power production and consumption, while satisfying power grid constraints. However, this approach focuses on the transmission level, whereas we consider the distribution-level power grid to be at a much more imminent risk of congestion. At the transmission level, the scale is much larger than at the distribution-level, both geographically and considering the power levels involved. Moreover, the power grid has a very different topology at the transmission level. A major drawback of this approach when applied at the distribution-level, is that using a global power price for congestion mitigation is not only unfair for agents in non-congested areas, but it would also be converging to a solution much too slowly. A similar approach to the negotiated dispatch is provided by (Binetti et al. 2014) in which a gradient descent on the pricing is used, followed by a local optimization of agents.

Another approach is given by (Klauw et al. 2016), in which power programs are proposed by device agents that are able to satisfy cluster constraints to reach a target energy consumption, while also staying within the limits of the grid. In their approach, called Profile Steering, agents are only motivated to accomplish the cluster goal, which is to consume or produce energy at a specific target amount, and will propose alternative power programs whenever constraints are violated. Proposals that reduce the constraint violations the most, are then selected as the new candidate programs. In our view, the problem of this approach lies in the lack of motivation for the participant to sacrifice private rewards for running an alternative program. The only objective is the cluster goal, which means that the price of having limited resources is paid by a select set of individuals that offer the most flexibility, or conversely, the profit is reaped by those who are able to maximally make use of remaining capacity.

The authors of (Fioretto et al. 2017) propose an approach based on DCOPs (Distributed Constraint Optimization Problem) to solve the economic dispatch problem, as well as the real-time demand-response balancing problem. Their algorithm is able to find optimal solutions for a system of controllable generators and (predicted) loads, taking into account transmission network constraints. They show that finding the optimal solution using Dynamic DCOPs is possible, but their solution does not scale very well. A relaxed version of the problem, in which soft constraints may be (temporarily) violated, scales better, but still for relatively small time horizons, even considering their implemented solution on a GPU.

We note that related work on the topic of this chapter listed here is not exhaustive. For further detailed background, a comprehensive overview of different mechanisms for solving optimization problems in smart grids, particularly where demand response is involved, we refer to (Vardakas, Zorba, and Verikoukis 2014; Parhizi et al. 2015; Jordehi 2019).

6.3 Self-Organizing Economic Dispatch

In order to solve the problem defined in [eq:lprh:optim], we propose a heuristic self-organizing method for coordinating the power scheduling of smart grid devices on the distribution-level energy grid. This multi-agent based approach allows for great scalability, while ensuring privacy and final control of the end-user.

At the distribution grid level, devices are typically consumer devices, such as PV-panels, household batteries, heat pumps, ventilation or air-conditioning units. The controllability, or flexibility of such devices is often limited, and bound by the device limitations and the user preferences. With increasing numbers of such devices, using a strictly “top-down” approach is intractable, since the search space grows exponentially with each added device. For this reason we use a hierarchical approach, in which the market operator delegates its task to intermediate “congestion” agents which then independently solve subproblems—which is to make sure that the total power throughput at their allocated point does not exceed a certain threshold. Making such subdivisions is justified, since in the power grid, transformers are effectively branches of the topology, and two nodes under different transformers are independent of one another; hence, transformers are the logical point to place congestion agents in the control hierarchy.

Our approach, denoted as Local Pricing Receding Horizon (LP-RH) is based on the economic incentive that end-user devices should have, to provide its owner with a service, in the most affordable way. Put differently, the system will use price differences to stimulate agents to schedule their power consumption or production in a balanced way, such that any grid constraints are satisfied. The overall scheme is simply to gather expected power programs from the connected devices, and then iteratively adjust energy prices to steer the agents into a certain power program. The method is explained in more detail in the following section, and is similar to the Negotiated Price Dispatch proposed by (Warrington, Mariéthoz, and Morari 2011).

6.3.1 Local Pricing Receding Horizon

Figure 6.1: The principle of a receding horizon market is that every time step the time horizon for optimization shifts by one. Planned power programs (white) are turned into fixed contracts for the current time step (green), which determines the outcome of the algorithm. This figure is redrawn from (Warrington, Mariéthoz, and Morari 2011).

In order to create a power planning taking into account forecasts and/or predicted power programs of clients, we use a Receding Horizon (RH) approach, depicted in Figure 6.1 which means that at any point we only take a fixed horizon of TT program time units (PTU) into account. A PTU is typically 15 minutes or one hour, throughout this paper we will use PTU length of one hour so T=24T=24. However, none of the mentioned approaches are limited to this convention. When the algorithm has converged and a power program is found for the next TT PTUs that satisfies all constraints, the first PTU becomes the “current” situation, and the projected power program becomes a contract. The time horizon now shifts by one, and the entire system starts again.

Algorithm 5: LP-RH Algorithm

| Require: ii {Run for this agent ii}
| Require: 𝛒\mathbf{\rho} {For a given price 𝛒\mathbf{\rho}}
1: | if ii is a PV, load or storage agent then
2: |     𝑥i=arg min𝑥𝒞i(𝑥,𝛒)\mathit{x}_{i} = \text{arg min}_{\mathit{x}} {\mathcal{C}_{i}(\mathit{x},\mathbf{\rho})} {Run local optimization}
3: | else
4: |     repeat
5: |         for all j∈ℳij\in \mathcal{M}_i
6: |             𝑥j=𝐿𝑃−𝑅𝐻(j,𝛒)\mathit{x}_{j} = \mathit{LP}-\mathit{RH}(j, \mathbf{\rho}) {Recurse for child agents}
7: |         end for
8: |         𝑥i=∑j∈ℳi𝑥j\mathit{x}_i= \sum_{j\in \mathcal{M}_{i}}{\mathit{x}_j}
9: |         𝛜=𝒞i(𝑥i)\mathbf{\epsilon}= \mathcal{C}_{i}(\mathit{x}_{i})
10: |         𝛒=𝑎𝑑𝑗𝑢𝑠𝑡𝑃𝑟𝑖𝑐𝑒𝑠(𝛜,𝛒)\mathbf{\rho}= \mathit{adjustPrices}(\mathbf{\epsilon}, \mathbf{\rho}) {Gradient descent, see end of Section 6.3.1}
11: |     until 𝛜≤ϵmax\mathbf{\epsilon}\leq \epsilon^{\text{max}}
12: | end if
13: | return 𝑥i\mathit{x}_{i}

The Local Pricing Receding Horizon algorithm is shown as pseudocode in Algorithm 5; an example graph on which the algorithm could run is shown in Figure 6.2. The algorithm describes how any agent finds a new power program 𝑥i\mathit{x}_{i} to satisfy its local constraint 𝒞i\mathcal{C}_{i}. Every device agent in the grid does this by solving a local optimization problem (line 2), taking into account local constraints as explained in Section 6.3.2.

Figure 6.2: Simple example topology of a graph which could be running the LP-RH algorithm. One market operator (MM) is connected to two congestion agents (CiC_i), which are connected to a total of five device agents (DiD_i). The device agents can represent PV panels, consumer loads, storage agents, or any other leaf nodes in the power grid. Topologies where congestion agents are connected to more congestion agents are also possible.

Prices 𝛒\mathbf{\rho} are updated by the market operator agent and the congestion agents in order to get a power program 𝑥\mathit{x} satisfying the grid constraints. When the market operator or any congestion agent runs the LP-RH algorithm, all j∈ℳij\in \mathcal{M}_i, where ℳi\mathcal{M}_i are the immediate children of agent ii, are requested to propose a power program based on the price 𝛒\mathbf{\rho} (line 6). Here the function is called recursively until all agents have determined a new power program. Note, that if any of the children are congestion agents, they determine their power program by forwarding the prices to their children and returning the sum of all received programs. Many agents will not know exactly how they will function in the future, as contexts might change, a user might behave differently than anticipated, or weather conditions may act up; this is why receding horizon method updates the time iteratively. With the sum of all power programs, the market operator can determine the error 𝛜\mathbf{\epsilon}, which is the sum of all local constraint violations 𝒞\mathcal{C} for every t∈Tt\in T.

In line 9 the constraint 𝒞i\mathcal{C}_{i} is used to compute the local constraint violation and stored as an error variable 𝛜\mathbf{\epsilon}. The value of 𝛜\mathbf{\epsilon} is taken into account to adjust the prices in line 10. In the function 𝑎𝑑𝑗𝑢𝑠𝑡𝑃𝑟𝑖𝑐𝑒𝑠(𝛜,𝛒)\mathit{adjustPrices}(\mathbf{\epsilon}, \mathbf{\rho}), a gradient descent approach is used, which linearly interpolates the last two errors as a function of the price. We then choose the price at which the error is projected to reach zero. Note that this means we assume the reaction of the devices linearly depends on the prices, which will only hold under very specific circumstances. To overcome this issue, we iteratively repeat the process until 𝛜≤ϵmax\mathbf{\epsilon}\leq \epsilon^{\text{max}} and assume that a non-linear response can be described as a series of linear pieces. The parameter ϵmax\epsilon^{\text{max}} then represents an upper bound on the error, which we can use as a convergence criterion.

6.3.2 Agent Behavior

Agents in the system are characterized by the device that they have to assign a power program for. In the distributed case, every agent locally optimizes a local cost function JiJ_i, which is part of the global optimization problem [eq:lprh:optim]. Also, local constraints 𝒞i\mathcal{C}_i have to be taken into account which are represented by constraint [eq:lprh:constraint:agent]. The behavior of the agents can be defined by three functions for the costs, the local constraint and the power program; an overview of this is shown in Table 6.3. In our model we consider the following types of agents.

Table 6.2: A summary of the three functions specifying the behaviors of the agents.

Agent type | Cost | Constraint | Power
Market Operator | JMO=0J^{\text{MO}} = 0 | 𝒞MO=𝑥‾−𝚯\mathcal{C}^{\text{MO}} = \bar{\mathit{x}} - \mathbf{\Theta} | 𝑥‾=∑i∈𝒩𝑥i\bar{\mathit{x}} = \sum_{i\in \mathcal{N}}{\mathit{x}_i}
Congestion agent | JiCO=0J^{\text{CO}}_i= 0 | 𝒞CO=𝑥i‾−bi iff |𝑥i‾|<bi\mathcal{C}^{\text{CO}} = \bar{\mathit{x}_i} - b_i\text{ iff } |\bar{\mathit{x}_i}| < b_i | 𝑥i‾=∑j∈ℳi𝑥j\bar{\mathit{x}_i} = \sum_{j \in \mathcal{M}_i}{\mathit{x}_j}
Load agent | JiLOAD=0J^{\text{LOAD}}_i= 0 | 𝒞iLOAD=0\mathcal{C}^{\text{LOAD}}_i= 0 | 𝑥i\mathit{x}_i
PV agent | JiPV=𝑥i−𝑥′iJ^{\text{PV}}_i= \mathit{x}_i- \mathit{x}'_i | 𝒞iPV=0 iff τ𝑥i𝛒≥γi\mathcal{C}^{\text{PV}}_i= 0 \text{ iff } \tau\mathit{x}_i\mathbf{\rho}\geq \gamma_i | 𝑥i=𝑥′i or 0\mathit{x}_i= \mathit{x}'_i\text{ or } 0
Storage agent | JiST=𝑥i(1−η′i)J^{\text{ST}}_i= \mathit{x}_i(1-\eta'_i) | 𝒞iST=0 iff eimin<𝑒i<eimax\mathcal{C}^{\text{ST}}_i= 0 \text{ iff } e^\text{min}_i< \mathit{e}_i< e^\text{max}_i | 𝑥i=f(𝛒)\mathit{x}_i= f(\mathbf{\rho})

6.3.2.1 Market Operator

This is the root node of the tree (MM in Figure 6.2), as far as the local distribution grid concerns. In the physical grid, it corresponds to the transformer that connects the local low voltage (LV) grid to the medium voltage (MV) grid. We assume that there is no energy loss at the market operator, so JMO=0.J^{\text{MO}} = 0. Its goal is to find a solution to [eq:lprh:optim], and its private cost would be the same as the target constraint in [eq:lprh:constraint:target]. The market operator runs Algorithm 5, using a deviation of the target profile 𝚯\mathbf{\Theta} as an error, which is minimized by the algorithm. Hence, its local constraint is defined as 𝒞MO=𝑥‾−𝚯,\label{eq:lprh:marketoperator_constraint} \mathcal{C}^{\text{MO}} = \bar{\mathit{x}} - \mathbf{\Theta}, where 𝑥‾\bar{\mathit{x}} denotes the power program of the market operator. Since the market operator is not a device in the grid itself, its power is the sum of the powers of its children, which in case of the market operator are all nodes in the cluster 𝑥‾=∑i∈𝒩𝑥i.\bar{\mathit{x}} = \sum_{i\in \mathcal{N}}{\mathit{x}_i}.

The value of [eq:lprh:marketoperator_constraint] can either be negative or positive, which respectively means either the total power production or the total consumption is too high. The market operator sets an initial price of 𝛒=0.5\mathbf{\rho}= 0.5 for all PTUs, and then uses Algorithm 5 to minimize the constraint value until it reaches zero, in order to satisfy the global constraint [eq:lprh:constraint:target].

6.3.2.2 Congestion Agent

This is an intermediate node on the grid tree (CC in Figure 6.2) connected to a parent node who is either the market operator or another congestion agent. It corresponds to a component in the grid where congestion might potentially occur, such as a transformer. Equivalently to the market operator, we assume that no energy is lost here, so JiCO=0.J^{\text{CO}}_i= 0.

This agent has a constraint that aims to limit the power usage of that part of the grid, this corresponds to the constraint [eq:lprh:constraint:grid]. The congestion agent also uses Algorithm 5 to minimize the error of its local constraint, which is defined as 𝒞iCO={𝑥i‾−bi,if |𝑥i‾|≥bi,0,otherwise.\label{eq:lprh:concentrator_cost} \mathcal{C}^{\text{CO}}_i= \begin{cases} \bar{\mathit{x}_i} - b_i, & \text{if } |\bar{\mathit{x}_i}| \geq b_i, \\ 0, & \text{otherwise}. \end{cases} Here bib_{i} is the congestion threshold of the agent ii, which means it is the maximum power throughput of the grid at the point that ii represents. Again 𝑥i‾\bar{\mathit{x}_{i}} denotes the power program of the congestion agent, but is now equal to the sum of all devices under the current node 𝑥i‾=∑j∈ℳi𝑥j,\bar{\mathit{x}_i} = \sum_{j \in \mathcal{M}_i}{\mathit{x}_j}, Similar to the constraint of the market operator in [eq:lprh:marketoperator_constraint] the constraint value can become negative or positive, and is used to compute the error 𝛜\mathbf{\epsilon} in Algorithm 5.

6.3.2.3 Load Agent

This is an agent responsible for an uncontrollable load in the grid (represented by any device agent DD in Figure 6.2). This could be a consumer household, an office, street lighting, or any other non-flexible load, and thus only participates in the problem as part of constraint [eq:lprh:constraint:target]. In the distributed system however, it is responsible for making a forecast of the power usage, and this forecast will be updated with more accurate information as the time horizon shifts. The load agent has no attached cost in the global problem, and no need to locally compute any optimal behavior. This is equivalent to stating that its cost and constraint correspond to JiLOAD=0,J^{\text{LOAD}}_i= 0, 𝒞iLOAD=0.\mathcal{C}^{\text{LOAD}}_{i} = 0. Its corresponding load profile 𝑥i\mathit{x}_{i} is fixed to some profile that constrains the global problem [eq:lprh:optim]. In our experiments its values are taken from real households as described in Section 6.4.2.

6.3.2.4 PV Agent

For a PV agent 𝑥i\mathit{x}_i denotes the amount power produced in the time horizon. The PV agent (any DD in Figure 6.2) has some flexibility to offer to the optimization function [eq:lprh:optim] by allowing curtailment in reference to the expected generation. We assume that curtailment is binary, in that either the PV generates power as normal, or it is switched off and produces no power at all. Curtailing means that there is potential energy lost, and hence the cost function of a PV agent is defined as JiPV=𝑥i−𝑥′i,J^{\text{PV}}_i= \mathit{x}_i- \mathit{x}'_i, where 𝑥′i\mathit{x}'_i indicates the expected power, when not curtailing. This expected power is taken from the scenario, which will be detailed in the Section 6.4.

When reacting to prices in the distributed system, a decision is made in order to decide whether to curtail based on the price profile. If the operational running costs γi\gamma_{i} of the PV is more than the power that would be generated by it, there is no point in running the generator (from an economic point of view). Hence, the local constraint and its corresponding decision rule of a PV agent can be written as 𝒞iPV={1,if τ𝑥i𝛒<γi,0,otherwise,\mathcal{C}^{\text{PV}}_{i} = \begin{cases} 1, & \text{if } \tau\mathit{x}_i\mathbf{\rho}< \gamma_i, \\ 0, & \text{otherwise}, \end{cases} 𝑥i={0,if τ𝑥′i𝛒<γi,𝑥′i,otherwise.\mathit{x}_i= \begin{cases} 0, & \text{if } \tau\mathit{x}'_i\mathbf{\rho}< \gamma_i, \\ \mathit{x}'_i, & \text{otherwise}. \end{cases} For the PV agent it also holds that the corresponding expected power program 𝑥′i\mathit{x}'_{i} determines the global problem [eq:lprh:optim]. Its values in our experiments are taken from real PV panels as described in Section 6.4.2.

6.3.2.5 Storage Agent

In the context of storage, 𝑥i\mathit{x}_i denotes the planned charge and discharge actions in the time horizon. A storage agent (again a leaf node DD in Figure 6.2) provides flexibility by allowing to store some energy in a local storage like a battery or a heat buffer. There are limits to the amount of energy that can be stored, either because of the physical limitations of the storage device, or because of the end-user settings. Moreover, a storage agent has some efficiency, which defines energy loss when energy is put into it, or out from it. This means that we can define the cost function of the storage agent as the energy lost during charging or discharging JiST=𝑥i(1−η′i),J^{\text{ST}}_i= \mathit{x}_i(1-\eta'_i), where η′i={ηi,if 𝑥i≥0,ηi−1,otherwise.\eta'_i= \begin{cases} \eta_i, & \text{if } \mathit{x}_i\geq 0, \\ \eta_{i}^{-1}, & \text{otherwise}. \end{cases} This difference makes sure that the loss is correlated to the internal power of the battery when charging or discharging. Put differently, 𝑥i\mathit{x}_i defines the power at the grid side of the storage, and when an agent is charging, a lower power effectively charges the battery, and conversely when discharging a higher power is required to provide some power level to the grid.

In order to define the constraints of the storage agent we must define the update function for the amount of energy 𝑒i\mathit{e}_{i} stored as the cumulative sum of the powers eit=ei0+τ∑t′=t0t′=tη′i𝑥it′−λi.e_{i{}t} = e_{i0} + \tau\sum_{t'=t_0}^{t'= t}{\eta'_i\mathit{x}_{it'} - \lambda_i}. Here λi\lambda_i represents the leakage or self-discharge rate of the storage agent ii, and ei0e_{i0} is the stored energy at the start of the experiment. Let us now define the following constraints on the storage agent 𝒞iST={0,if eimin<𝑒i<eimax,1,otherwise.\mathcal{C}^{\text{ST}}_{i} = \begin{cases} 0, & \text{if } e^\text{min}_i< \mathit{e}_{i} < e^\text{max}_i, \\ 1, & \text{otherwise.} \end{cases} The minimum and maximum energy values are defined by eimine^\text{min}_i and eimaxe^\text{max}_i, respectively.

For a storage device, the power limits denote the maximum charge and discharge rates. They are defined by ximaxx^\text{max}_i and ximinx^\text{min}_i, respectively, in [eq:lprh:constraint:power]. A special case of a storage device is a heat pump, which (electrically powered) heats a house in order to keep the temperature within comfortable levels. The heat pump only allows charging and only discharges through leakage, hence for a heat pump ximin=0x^\text{min}_i= 0 and λi>0\lambda_i> 0.

When a storage agent has to update its expected power program in line 2 of Algorithm 5, some response function (f(𝛒)f(\mathbf{\rho}) in Table 6.3) is required, which is “economically sane” and has the following characteristics:

return ximaxx^\text{max}_i for low prices and ximinx^\text{min}_i for high prices,

be a monotonically decreasing for increasing prices,

have a “plateau” of zero power response for some intermediate price (𝛒=0.5\mathbf{\rho}= 0.5), which is wider for less efficient devices.

The final characteristic allows more efficient devices to respond to subtle price change, and have less efficient devices respond to more extreme prices. This way devices with a higher efficiency are used first when flexibility is needed, and (when parameterized correctly) less efficient devices will only be used when required. In our implementation we chose a relatively simple response, defined by four points in the price domain:

ρ1=ρ2−ζ\rho_1 = \rho_2 - \zeta, the highest price at which the device will use the maximum charge rate (𝑥i=ximax\mathit{x}_i= x^\text{max}_i),

ρ2=ηi/2\rho_2 = \eta_i/ 2, the lowest price at which the device will not charge or discharge (𝑥i=0\mathit{x}_i= 0),

ρ3=1−ρ2\rho_3 = 1 - \rho_2, the highest price at which the device will not charge or discharge (𝑥i=0\mathit{x}_i= 0),

ρ4=ρ3+ζ\rho_4 = \rho_3 + \zeta, the lowest price at which the device will use the maximum discharge rate (𝑥i=ximin\mathit{x}_i= x^\text{min}_i),

where ζ\zeta is an arbitrary constant that defines the interval in which the agent linearly decreases its power response between the price points. By choosing the points in this way, we follow the requirements as specified before, and we can ensure that two types of devices, that have an efficiency ηi\eta_i difference of more than ζ\zeta will be put to use separately. This power/price relation we chose for our numerical evaluation with ζ=0.075\zeta = 0.075 is depicted in Figure 6.3.

An alternative strategy for the storage agent would be to make use out of any differences in the price, charging and discharging as soon as the price differences are large enough to overcome its efficiency. From a strictly economic perspective, this is the optimal strategy to maximize its own benefit. However, this leads to very “binary” behavior with minimal and maximal charging rates (Li, Chen, and Low 2011) and thus, little room for optimizing from the market operator and congestion agent. Therefore, a linear strategy is implemented as depicted in Figure 6.3, allowing to solve the overall optimization problem [eq:lprh:optim].

Figure 6.3: The strategy of the storage agent with ximax=200x^\text{max}_i= 200 W, ximin=−100x^\text{min}_i= -100 W and ηi=0.9\eta_i= 0.9 shows the power response for an increasing price. The plateau at 0 W extends from 𝛒=ηi/2\mathbf{\rho}= \eta_i/ 2 to 𝛒=1−ηi/2\mathbf{\rho}= 1 - \eta_i/ 2.

6.4 Experiment Setup

The LP-RH algorithm was empirically evaluated by running simulations of an LV grid with a set of realistic household load profiles and PV production profiles for a series of 24 PTUs. Simulations were randomized by selecting different load and production profiles, and random households were selected to have a heatpump or a household battery. The simulations are implemented in Matlab, and require around 30 seconds to simulate a single day. More information about the different implementation details are specified below.

6.4.1 Distribution Network Topology

For the topology of the network we use the European Low Voltage Test Feeder (IEEE 2015) network. This dataset is used to benchmark power and energy algorithms on realistic European distribution networks. In this chapter we superimposed six points on the topology, where we monitor and mitigate any potential congestion. These points are strategically chosen to separate the problem into independent subproblems. The resulting topology with the congestion points are shown in Figure 6.4.

Figure 6.4: The topology of the IEEE LV feeder network used for the simulation. The figure depicts the connections between household consumers, the intermediate congestion agents, and the root market operator. The PV, load and storage agents are randomly placed at the households for different simulation runs. The “filled” markers represent the agents displayed in Figures 6.5–6.7.

6.4.2 Household Load and PV Profiles

The household consumption and production profiles are taken from a pilot study (Rassa et al. 2019), in which 92 residential consumers were monitored over the course of a year (from March through November 2018). The data was preprocessed such that we have separated information on the consumption of houses, and of the PV installations. Data is anonymized and randomized per month, so that we can select data from any specific month for a base load of a household, or a residential PV installation.

In the experiment the 54 households from Figure 6.4 were assigned a random instance of the load and PV profiles from the same month (i.e. all households were equipped with PV panels). The daily load consumption varied between 4.98 kWh and 29.39 kWh, and the total PV production varied between 826 Wh and 18.8 kWh. Furthermore, 16 randomly selected households were assigned a household battery, and again 16 were chosen to have a heat pump installation.

Every household and PV installation in the simulation would select a random profile from the dataset, which was used as its power program. The objective 𝚯\mathbf{\Theta} was set to a total net consumption of the LV grid using the mean total power consumption of the houses including PV production. Choosing the target profile 𝚯\mathbf{\Theta} in this way corresponds to a situation in which the energy provider of the simulated neighborhood would agree to a contract for the average behavior of the households, and subsequently attempts to use flexibility to account for any deviations from the normal.

The batteries were all dimensioned with storage capacities of emax=10.8e^\text{max}= 10.8 kWh, and maximum charge and discharge rates of xmax=4000x^\text{max}= 4000 W and xmin=−4000x^\text{min}= -4000 W, respectively. The batteries charging efficiencies were all set at η=0.9\eta=0.9. The heat pumps were estimated to have a working energy capacity of emax=2e^\text{max}= 2 kWh, this means the difference between the thermal energy capacity of the house at the minimum and maximum comfortable user temperature is 2ψ2 \psi kWh, where ψ=4.0\psi= 4.0 is the coefficient of performance of the heat pump. Then, the heat pumps have a xmax=1600x^\text{max}= 1600 W and xmin=0x^\text{min}= 0 W, an efficiency of η=1\eta= 1 and a constant leakage rate of λ=360\lambda= 360 W. Finally, to ensure convergence, the maximal error value is set to ϵmax=10−3\epsilon^{\text{max}}=10^{-3} in the experiments for this chapter

6.4.3 Forecast Uncertainty

The predicted load and production power programs 𝑥̂\hat{\mathit{x}} of the load and PV agents were generated by taking average profiles of the complete dataset. These average profiles are considered as taken from historic data and hence, provide a ground for predicting the power program of future PTUs. When agent ii determines its power prediction 𝑥′i\mathit{x}'_i, it will compute a weighted average between its assigned power program 𝑥i\mathit{x}_i and the average profile 𝑥̂\hat{\mathit{x}}, such that 𝑥it=(1−α)𝑥′it+α𝑥̂t,α=t−1T−1,\begin{aligned} \label{eq:lprh:forecast} \mathit{x}_{i{}t} &= (1-\alpha) \mathit{x}'_{i{}t} + \alpha \hat{\mathit{x}}_{t}, \\ \alpha &= \sqrt{\frac{t-1}{T-1}},\end{aligned} such that at t=1t= 1 the prediction equals the selected profile 𝑥′it\mathit{x}'_{i{}t}. At t=Tt= T, the prediction is simply the average power 𝑥̂t\hat{\mathit{x}}_t.

6.5 Centralized Solver

In order to address the performance of the LP-RH algorithm, a centralized optimization approach is also introduced to provide lower bounds to its results. A mixed integer linear program (MILP) solver was used to find these bounds for the problem stated in [eq:lprh:optim]. The centralized optimization approach considers the exact same scenario that was solved by the decentralized algorithm; the energy loss is minimized and the same set of constraints apply. A fundamental difference lies in the availability of information. Whereas detailed information is only shared locally in the LP-RH algorithm, the centralized optimization approach assumes complete knowledge of the current system state for the decision-maker; i.e., no limits are imposed on the spacial flow of information within the network. With these features in mind, two versions of the MILP were formulated: Receding Horizon Centralized Solver and Perfect Information Centralized Solver.

6.5.1 Receding Horizon Centralized Solver

The receding horizon centralized solver (RHCS) is the most similar to the LP-RH algorithm. It uses a receding horizon approach (as depicted in Figure 6.1) to find an ideal dispatch solving the consecutive sub-problems. Uncertainty about future device states is again simulated by [eq:lprh:forecast]. Because this solver has perfect information at the current state for each iteration of the receding horizon, its solution represents a lower bound on the solution found by the LP-RH algorithm.

6.5.2 Perfect Information Centralized Solver

In the perfect information centralized solver (PICS), a single centralized optimization problem is solved for the complete dispatch. In addition to perfect spacial information, this version of the MILP also has perfect temporal information about the complete system state; this means that no uncertainty about future states is simulated. Referring back to [eq:lprh:forecast], this is equivalent to setting α=1\alpha = 1, which results in perfect predictions for each profile. The solution of this MILP represents an absolute lower bound for problem [eq:lprh:optim].

6.6 Results

Figure 6.5: The power program of the market operator and the price profile as the outcome of Algorithm 5, show the results of a 24-hour simulation of the problem with the LV feeder network and 92 random households.

Figure 6.6: The power program of a congestion agent shows some periods of congestion at the production and consumption bounds (red dashed lines), and the corresponding changes in price profiles (from Algorithm 5) relative to the global price of the market operator.

In this section the results of the described experiments are shown. Before comparing the performance of the different solvers, which is done in Section 6.6.1, the behavior of the LP-RH algorithm is shown in this section. The graphs in this section show examples of single simulation runs—subject to randomized starting conditions—demonstrating the behavior of the different agent types. Powers are shown as power consumption, this means a net consumption is shown as positive power, and conversely negative powers indicates a net power production. In Figure 6.5 the final result of the market operator is shown, where the market operator has found a price profile such that the target profile is met exactly.

Figure 6.6 shows the power program of one of the three congestion agents that is directly connected to the market operator. Its power congestion limits are set such that in the peak moments of the day there is some congestion expected. This results in a price difference shown in the power program, as around the peak PV production (t=12,13,14t= {12, 13, 14}) the local price is slightly lower than the market price, leading to a lower net power production. Similarly, we can identify that at the end of the day (t=19,20,21,22t= {19, 20, 21, 22}) a positive power congestion was mitigated by increasing the price.

Figure 6.7: The power program of a heat pump agent shows the power being mostly used at moments where the price is low, relieving the need to charge when the price is high; or considering the view of the grid, when a lower power consumption is required.

The power program of a heat pump agent is shown in Figure 6.7. This heat pump is connected directly to the congestion agent, the results of which are shown in Figure 6.6, hence its price profile should be identical. What is most obvious in this graph is that the high price at t=12t= 12 leads to a zero power consumption, and quickly after that, the power consumption rises in order to maintain comfortable temperatures. Again, around t=19,20,21t= {19, 20, 21} the relatively high prices lead to a power consumption of zero, which was apparently feasible because of the high power consumption leading up to it.

Figure 6.8: The total power consumption per device type show that the batteries are used far less than the heat pumps, since they have a lower efficiency. The PV panels did not have to be curtailed in this run.

Finally, Figure 6.8 shows the total power programs of all devices in this experiment summed up. In this figure, the power programs of the loads and the PVs are the direct result of the chosen profiles, and are the input for problem [eq:lprh:optim]. We can see that for the majority of the experiment, all used flexibility is from the heat pumps with the high efficiency. Only at times of the congestion will the less efficient battery agents be used.

6.6.1 Comparison with Central Solvers

Figure 6.9: Compared with centralized optimization solvers, the LP-RH algorithm performs equally well. In this boxplot the median is shown as a line, the boxes indicate the 25% and 75% percentiles, and the tails are capped at a maximum length of the box width; outliers are drawn separately.

In a validation experiment 105 random problem instances (15 permutations for seven months) were created, and solved by the three different algorithms. In Figure 6.9 the results are shown for the feasible instances. A solution is considered feasible if all three solvers were able to find a solution that satisfies all constraints. The LP-RH algorithm did not find a correct solution for 26 problem instances, 11 of which were found to be overconstrained according to RHCS. For the feasible instances the LP-RH algorithm found solutions that were not significantly worse than the PICS, and in 21 instances found a solution with the exact same cost. In 27 instances LP-RH found a solution that was equally well as the RHCS or even slightly better—this seems to contradict the initial statement that RHCS acts as a lower bound for LP-RH; however, this is due to the way both solvers deal with uncertainty. The LP-RH algorithm allows the congestion agents to violate power constraints for future PTUs (t>1t> 1), but not for the next PTU (t=1t= 1), by allowing an additional error margin for future PTUs. The rationale is that we do not want to focus on potentially imperfect forecasts according to [eq:lprh:forecast], as long as we ensure that eventually PTUs are not congested. The RHCS algorithm does not allow power constraints to be violated at any point in the future, and hence might react too strict when a future congestion is predicted, but does not actually occur.

In the set of infeasible problems, i.e. problems that do not have a valid solution satisfying all constraints, LP-RH does find solutions that minimize the power loss. However, since these solutions temporarily overload congestion agents (where 𝑥i>bi\mathit{x}_i> b_i), or does not match the target profile 𝚯\mathbf{\Theta} exactly, they are not a fair comparison, since they do not strictly solve [eq:lprh:optim]. In a separate run the problems were relaxed, by increasing the congestion thresholds of the congestion agents. This resulted in the LP-RH not being able to find a solution in only 14 problem instances, but the results were otherwise similar to the ones reported here in Figure 6.9.

6.7 Conclusions

Implementing a self-organizing multi-agent system for smart grids requires new dispatch algorithms, that do not rely on centralized control. In Chapter 2, we showed how a framework for self-organization can be used by a system to change its deployment, but still had no way to reason about the configuration itself. The LP-RH algorithm for power dispatch is just that: an algorithm for distributed decision-making. Note, that the algorithm is specifically written to optimize the problem at hand, although the underlying principles can apply to other problems.

We have introduced an algorithm for self-organization, by solving the economic dispatch problem using a decentralized market based approach with local pricing. The LP-RH algorithm using a hierarchical approach was shown to be able to solve the problem using a fairly simple interaction scheme in which pricing information is sent down the hierarchy tree, and planned or forecasted power programs are sent back up. Using a gradient descent approach, the market operator is capable of tuning the pricing to find feasible solutions to minimize the power losses in the grid.

In our experiments we found that in 20% of the problems LP-RH did not perform any worse than a perfect-information centralized solver. In the other 80% our algorithm did not perform significantly worse. The benefit of LP-RH over a centralized solver are in the robustness and scalability of the solution, as well as in the preserved privacy of the end-consumers.

In the implementation of the response of the storage agent, we intentionally did not choose to respond with an optimal power program given the price signal. Particularly, when a high price is expected in the future, the agent will not “proactively” charge to avoid having to charge later, or vice versa. This behavior could be implemented at the agent quite easily using a dynamic programming approach, but it would lead to very extreme behavior, e.g. very binary behavior of charging or not-charging at full capacity even for small price differences. This binary behavior is hard to deal with in the rest of the hierarchical tree, and does not lead to any problems per se, but might be improved upon in a future continuation of this work.

Other variations of the problem may include other device types, for instance time-shiftable devices such as washing machines or dishwashers. Also, using electric vehicles (EV) as an additional type of agent, providing energy flexibility is a very interesting extension, which will undoubtedly lead to other complications because of their high power ratings (i.e. they dominate the total power consumption when charging). Finally, an integration with a real time balancing algorithm such as (Kok and Subramanian 2019) would be very fruitful to complete the needs of the future smart grid.

In this chapter a very specialized method for driving the self-organizing behavior was provided, compared to a generic reusable DCOP-based approach in the previous chapters. The same underlying principle however is that through local interactions and decisions made on partial knowledge, a solution is sought to a global problem. In the next and final chapter we discuss the main outcomes of this thesis and look ahead to potential ways to extend this work.

7 Conclusions and Future Work

We can only see a short distance ahead,
but we can see plenty there that needs to be done.
—Alan Turing

In order to keep up with the quickly growing networks that exist today, we need to minimize human intervention and maximize self-dependency in order to keep systems operational. Self-organization is key when it comes to making a group of agents cooperates under varying conditions, achieving changing goals, while forming new teams. There exist already many methods for making systems more adaptive to changing operating conditions, but when a group of agents is involved that have to adapt to a new condition as a team, these methods do not always apply. In this thesis different topics were discussed that are required in order to attain or improve existing self-organizing behaviors to a system consisting of cooperative agents.

In Chapter 1, we asked the main question of this thesis:

How can we achieve self-organization, or improve the self-organization capabilities in a network of cooperative agents?

The answer to this question consists of two components, which are addressed in two challenges:

Challenge 1

Create a framework that allows self-organizing systems to redefine their deployment.

Challenge 2

Find or improve strategies to coordinate collective behavior.

Firstly, in this thesis we have proposed a framework for adding self-organization capabilities to multi-agent systems, specifically by adding a layer of intelligence to an agent, which is dedicated to making decisions on the configurations of the system at hand. We have shown that this framework provides the means of to reason about self-configuration, but it does not specify how to self-organize. Therefore, secondly, a reasoning mechanism is required, but there are different methods that allow to reason about such decisions. Throughout this thesis we have used three methods: logic based, distributed decision-making using DCOPs, and a market-based control algorithm. These three approaches are very different in their nature, and deciding when to use which approach depends largely on the problem at hand, the type of decision variables that can be altered, and the expert knowledge of the system designer.

We will further detail the outcomes of this thesis in the following section, addressing the main challenges as defined in Chapter 1.

7.1 Contributions

In Chapter 2, we addressed the first challenge: creating a framework that allows self-organizing systems to redefine their deployment. A framework for self-organizing multi-agent systems was proposed. Particularly, this framework was used to add self-organization to a sensor network, in which a group of sensors cooperates to estimate the state of a greenhouse climate. Using the provided mechanisms, agents are able to reason about the current context of the sensors and about how to most efficiently perform the task they were assigned. In the use case, a set of preexisting algorithms for performing the state estimation was provided, along with some knowledge about the conditions under which any method should be used and how it should be configured. The modular implementation of the framework, and the separation of the “primary path” from the “secondary path” allows the use of different reasoning techniques. The framework and corresponding tools are further detailed in (Leeuwen, Rieter-Barrell, et al. 2016; Leeuwen, Díaz, et al. 2016).

The second challenge was: finding or improve strategies to coordinate collective behavior. This challenge was addressed in Chapters 3 to 5 by using a solver for DCOPs and in Chapter 6 using a decentralized market based approach. Specifically, in Chapter 3 a new (A)DCOP algorithm called Cooperative Constraint Approximation (CoCoA) was introduced as one such candidate for reasoning about the primary task of an agent. The CoCoA algorithm is in its essence a simple mechanism to coordinate variable assignments in such a way that a local (1-hop) optimal assignment is being made. CoCoA is unique in its kind by not using an iterative approach to finding solutions, but instead finds a solution by spreading its activity through the problem graph, assigning values as it does so. Comparing this strategy to state-of-art DCOP algorithms showed that it not only reduced the communication overhead, but also finds solutions that are nearly equivalent in costs.

The original CoCoA algorithm was extended as CoCoA_CA in Chapter 4 in order to be applied to wireless power transfer networks. In this problem it is strictly not allowed to violate a hard constraint, stating that the total electromagnetic radiation can not exceed safe levels. By adding an extra check in CoCoA_CA to make sure neighboring agents do not assign a value concurrently, in which case they would not take the other assignment in consideration, these hard constraints are satisfied in all cases. We furthermore showed that even though CoCoA_CA does not perform as well as a centralized LP, the distributed mechanism is better capable of adapting the behavior of agents, when perfect information is not available.

Another shortcoming of CoCoA was addressed in Chapter 5: the fact that CoCoA only assigns a value once, makes it impossible to recover from early choices. We have shown that using CoCoA as an initialization strategy for other (iterative) DCOP solvers, we do not only improve on the convergence rate of these other solvers and on the solution cost of CoCoA, but also on the solution cost of the other solvers. This effect turns out to stem from the fact that in many graphs there are bridge edges (or pseudo-bridge edges), which connect clusters of connected vertices. When the nodes on such bridge edges are assigned values that violate the constraint on that edge, it is very hard for an iterative solver to overcome that initial assignment. CoCoA, and to a lesser extent zero-step-lookahead solvers, are unlikely to assign a constraining value on such edges, and thus allow for a better solution.

Although DCOPs are a way of implementing coordinated decision-making, it is not always the best approach to solving this problem—especially “fully-connected” problems, where variables share constraints with all other variables, are difficult to solve. Such problems can be described as a DCOP, but solving them as such is very inefficient. For this reason, in Chapter 6 we introduced another self-organizing mechanism, specifically for solving the Distributed Economic Dispatch problem, with flexible distributed energy resources. We have shown how this problem can be formalized and optimized using a decentralized multi-agent market-based approach, in order to minimize the energy loss, and maximize social wellfare.

7.2 Future Work

In this thesis we have presented some mechanisms to implement self-organization in a multi-agent system. The proposed techniques have shown to be able to make decisions autonomously of the functioning of the system, adapt to changes in the environment, without external intervention, and to find solutions that are near optimal. This relieves much work from human operators, but there are still many questions that remain unanswered. Based on our challenges from Chapter 1, we list some future research possibilities that we think should be addresses next.

Challenge 1: Create a framework that allows self-organizing systems to redefine their deployment. In Chapter 2, we proposed a framework for self-organizing systems in a state estimation context. This framework was founded on the principle of separation-of-concerns, and as such, few assumptions were made on the primary task of the system. The framework itself is quite conceptual, and lightweight. It could be extended by introducing more concrete mechanisms for implementation, and even add ready built modules and services. This will limit the flexibility, but may further alleviate tasks from the system designer. The benefits of such “frameworks” would undoubtedly exist, but are notoriously difficult to quantify.

Challenge 2: Find or improve strategies to coordinate collective behavior. A key contribution of this thesis is the CoCoA algorithm, and the hybrid solvers, which were shown to efficiently solve DCOP problems. However, different mechanisms for reasoning about self-organization were used in this thesis; we did not find a “one approach fits all” mechanism that works for any problem in all domains. If such an approach does exist, it would need to be able to learn about the problem at hand, instead of using an implicit or explicit model of the primary system. Examples of such a mechanism are sometimes referred to as Distributed Constraint Evaluation and Exploitation (DCEE) algorithms (Stranders et al. 2012; Nguyen et al. 2014) and may involve other machine learning methods such as Reinforcement Learning (Elidrisi et al. 2014; Lezama et al. 2019), but this was not addressed in this thesis. Alternatively, if such a “catch-all” mechanism does not exist, further research is needed to find self-organization mechanisms for different problem domains.

Finally, the problem of finding coordination strategies with a small overhead for multi-agent decision-making is one that applies in many problem areas (Lützenberger et al. 2016). The First Order Logic reasoner is quite lightweight, and the LP-RH market based mechanism also appears to scale well, but we have not validated these approaches in very large deployments. Also, CoCoA is an efficient solver compared to other DCOP algorithms, but there may be different graph structures or constraint types, on which this is not the case. In part, such drawbacks can be diminished using the Hybrid DCOP approach proposed in Chapter 5, but more research about the type of problems and the effects on CoCoA thereof would increase the usability of the method.

Acknowledgements

[acknowledgements]

I would like to thank my supervisors Koen Langendoen and Przemysław Pawełczak for their support and guidance. I will definitely remember Przemek’s motivating speeches, when things were looking down, and his joyful celebrations when we had good news. Thank you for all the efforts in co-authoring, proofreading and pushing me into writing the next papers and thesis chapters. I feel that we also got close personally, when there was anything on my mind, I could always reach you. Koen, thank you for your time and support and keen eye for detail, especially during the last stages of this thesis. And of course, thank you for giving me the opportunity to do my doctoral research in your group at the university.

I would also especially like to thank Zoltan Papp, who unfortunately is no longer with us, and did not get to see the results of his coaching. I will remember him as always being very enthusiastic and optimistic about his (and this) work, and has definitely helped me get on the right track to do my research and write this thesis.

Considering the SOSE project, many thanks go to Joris Sijs and Zoltan Papp for co-authoring the paper, and providing their expertise on state estimation. The project was a group effort as a part of the Adaptive Multi Sensor Networks (AMSN) TNO research program. Also, I would like to thank Julio Oliveira, Jan de Gier and Mark Zijlstra for their help with implementing the experiments. Furthermore, the project was made possible by Leon Kester, Ad van Heijningen and Paul Booij—thank you for your contributions.

The wireless power transfer chapter would not have been possible without the help of Kasım Sinan Yıldırım. Thank you very much for bringing the topic to my attention, and for providing this great application for my algorithm. I think we had a good time working together, and I can definitely say that writing this paper was the most fun of all the chapters in this thesis. Also, I have to thank you again for presenting the paper in Arizona when I couldn’t: you did a great job in presenting our work, and brought home the Best Paper award.

Considering the final chapter of my thesis, I would like to thank Arun Subramanian for his help with implementing the agent-based algorithm and experiments. I would like to thank Joost Stam for helping me with the formal definition of the problem and the following mathematical analysis. And of course thanks goes to Koen Kok, for providing the scientific guidance and expertise in the energy domain.

Then I would like to thank all the other TNO colleagues and former colleagues who helped me in shaping my research, either directly or indirectly, or by providing a relevant project or use case. A few people who I owe a special thanks for their contribution as a project leader that (partially) funded my research are Peter Laloli (AMSN), Yolanda Rieter-Barrell (DEMANES), Esther Zondervan (ERP Complexity) and Joost Adriaanse (CERBERO).

I would also like to thank all my colleagues at the TU Delft. Thanks for letting me be part of the group, even though I was sometimes not around for months on end, I always felt welcome and will remember the group outings. I would especially like to thank Andrei Pruteanu, who worked with me on the DEMANES project, and pointed me to DCOPs as a potential driver of self-organization. Also, I would like to thank Marco Cattani and Andreas Loukas for discussing my work, or telling me about theirs, or a chitchat about the more important things in life over a cup of coffee.

A special thanks goes to Elizabeth Busey who very kindly allowed me to use her artwork for the front cover of this thesis. Elizabeth uses the disciplines of printmaking, collage and alternative photography to explore the beauty of natural forms and their underlying mathematical and scientific explanations. See more of her work at http://www.elizabethbusey.com.

Outside my work environment, I would like to thank my dear friends Daan, Niels and Aljo and of course the JC, Folkert, Kees K., Kees L., Sjaak, Sjoerd and Wicher. Thank you for the good times, drinks and food, and all the city trips.

Obviously I would like to thank my parents Jan and Wyp, my sisters Jeanette and Marianne, and the rest of my family for their love and support. Because of you, I am the curious, investigative, problem-solving scientist that I am today. Also, I would like to thank my parents-in-law Arnold and Corine, for welcoming me into their family.

I would like to thank my loving wife, Inge. Thank you for your love and understanding and for the patience over the years. You have been my support for nearly twelve years now, and I hope you will for a long time after this. You know what it is like writing a dissertation, and you have helped me see it through. You have inspired me to keep putting my best into my work, and you will continue to do so. And of course I also have to thank you for bringing so much happiness into my life, which brings me to the last two people I would like to thank.

Alex en Chris, thank you for all your love and joy that you give me. You two are the best thing that happened to me, and you already make me and your mother very proud. Having you has definitely not helped to finish my thesis, but both of you are absolutely the best reason to get my mind off of it.

Curriculum Vitæ

07-10-1986
Born in Delfzijl, The Netherlands.

Education

2008–2010 | Master Artificial Intelligence
| University of Groningen
| Master Thesis: Driver Modelling and Lane Change Maneuver Prediction
| Supervisor: Dr. ir. B. Netten and Dr. M. A. Wiering
2004–2008 | Bachelor Artificial Intelligence
| University of Groningen
| Bachelor Thesis: Object Recognition Based on Local Symmetries
| Supervisor: Dr. G. Kootstra
1998–2004 | High School
| Ommelander College, Appingedam

Experience

2016 | Research Scientist
| TNO ICT,
| Monitoring and Control Services, Groningen
2012–2020 | Ph.D. Student (visiting researcher)
| Delft University of Technology,
| Embedded and Networked Systems
2010–2016 | Research Scientist
| TNO Technical Sciences,
| Intelligent Imaging, The Hague

List of Publications

[publications]

18

Publications related to this thesis

C. J. van Leeuwen, J. Sijs, and Z. Papp, A reconfiguration framework for self-organizing distributed state estimators, in Proceedings of the International Conference on Information Fusion (IEEE, Istanbul, Turkey, Jul. 9–12, 2013) pp. 499–506.

Chapter 2 of this thesis.

C. J. van Leeuwen, J. M. de Gier, J. A. de Oliveira Filho, and Z. Papp, Model-based architecture optimization for self-adaptive networked signal processing systems, in Proceedings of the International Conference on Self-Adaptive and Self-Organizing Systems (London, UK, Sep. 8–12, 2014) pp. 187–188.

C. J. van Leeuwen, Y. Rieter-Barrell, Z. Papp, A. Pruteanu, and T. Vogel, Model-based engineering of runtime reconfigurable networked embedded systems, in Runtime Reconfiguration in Networked Embedded Systems edited by Z. Papp and G. Exarchakos (Springer Singapore, 2016) Chap. 1, pp. 1–28.

Z. Papp, R. del Toro Matamoros, C. J. van Leeuwen, J. de Oliveira Filho, A. Pruteanu, and P. Šůcha, Designing reconfigurable systems: Methodology and guidelines, in Runtime Reconfiguration in Networked Embedded Systems, edited by Z. Papp and G. Exarchakos (Springer Singapore, 2016) Chap. 2, pp. 29–68.

C. J. van Leeuwen, V. H. Díaz, R. Kotian, R. del Toro Matamoros, Z. Papp, and Y. Rieter-Barrell. An illustrative application example: Cargo state monitoring, in Runtime Reconfiguration in Networked Embedded Systems, edited by Z. Papp and G. Exarchakos (Springer Singapore, 2016) Chap. 6, pp. 137–168.

C. J. van Leeuwen and P. Pawełczak. CoCoA: A non-iterative approach to a local search (A)DCOP solver, in Proceedings of the Conference on Artificial Intelligence (AAAI, San Fransisco, CA, USA, Feb. 4–11, 2017).

Chapter 3 of this thesis.

C. J. van Leeuwen, K. Sinan Yıldırım, and P. Pawełczak. Self adaptive safe provisioning of wireless power using DCOPs, in Proceedings of the International Conference on Self-Adaptive and Self-Organizing Systems (Tucson, AZ, USA, Sep. 18–22, 2017).

Chapter 4 of this thesis. This paper received the “Best Paper” award.

C. J. van Leeuwen and P. Pawełczak. Hybrid DCOP solvers: Boosting performance of local search algorithms, in Proceedings of the International Workshop on Optimization in Multiagent Systems (Stockholm, Sweden, Jul. 14, 2018).

Chapter 5 of this thesis.

A. Rassa, C. J. van Leeuwen, R. Spaans, and K. Kok. Developing local energy markets: a holistic system approach, IEEE Power and Energy Magazine 17(5):59–70 (2019).

Publications unrelated to this thesis

J. Baan, B. Driessen, J. van Huis, and C. J. van Leeuwen. SPITS road side sensor system, in Proceedings of the European Congress on Intelligent Transport Systems, (Lyon, France, Jun. 6, 2011).

H. Bouma, G. Burghouts, L. de Penning, P. Hanckmann, J. M. ten Hove, S. Korzec, M. Kruithof, S. Landsmeer, C. J. van Leeuwen, S. van den Broek, A. Halma, R. den Hollander, and K. Schutte. Recognition and localization of relevant human behavior in videos, in Sensors, and Command, Control, Communications, and Intelligence Technologies for Homeland Security and Homeland Defense, edited E. M. Carapezza, (Baltimore, MA, USA, Jun. 6, 2013) 87110B.

G. Burghouts, L. de Penning, J. M. ten Hove, S. Landsmeer, S. van den Broek, R. den Hollander, P. Hanckmann, M. Kruithof, C. J. van Leeuwen, S. Korzec, H. Bouma, and K. Schutte. A search engine for retrieval and inspection of events with 48 human actions in realistic videos, in Proceedings of the International Conference on Pattern Recognition Applications and Methods (Barcelona, Spain, Feb. 15–18, 2013) pp. 413–418.

C. J. van Leeuwen, A. Halma, and K. Schutte. Anomalous human behavior detection: an adaptive approach, in I. Kadar, editor, Signal Processing, Sensor Fusion, and Target Recognition (Baltimore, MA, USA, May 23, 2013) 874519.

B. Netten, I. Passchier, H. Wedemeijer, S. Maas, and C. J. van Leeuwen. Technical evaluation of cooperative systems experience from the DITCM test site, in Proceedings of the European Congress on Intelligent Transport Systems (Dublin, Ireland, Jun. 4–7, 2013).

B. Netten, A. Hegyi, M. Wang, W. Schakel, Y. Yuan, T. Schreiter, B. van Arem, and C. J. van Leeuwen. Improving moving jam detection performance with V2I communication, in Proceedings of the World Congress on Intelligent Transport Systems (Tokyo, Japan, Oct. 14–18, 2013).

I. Passchier, B. Netten, H. Wedemeijer, S. Maas, C. J. van Leeuwen, and P. P. Schackmann. DITCM roadside facilities for cooperative systems testing and evaluation, in Proceedings of the International Conference on Intelligent Transportation Systems (The Hague, Netherlands, Oct. 6–9, 2013) pp. 936–942.

C. J. van Leeuwen, J. van Huis, and J. Baan. Large scale track analysis for wide area motion imagery surveillance, in Optics and Photonics for Counterterrorism, Crime Fighting, and Defence, edited by D. Burgess, G. Owen, H. Bouma, F. Carlysle-Davies, R. J. Stokes, and Y. Yitzhaky (Edinburgh, UK, Sep. 26–28, 2016) 99950J.

P. Pillegi, J. Verriet, J. Broekhuijsen, C. J. van Leeuwen, W. Wijbrandi, and M. Konsman. A digital twin for cyber-physical energy systems, in Proceedings of the Workshop Modeling and Simulation of Cyber-Physical Energy Systems (IEEE, Montreal, Canada, Apr. 15, 2019).

References

Abdallah, Sherief, and Victor Lesser. 2008. “A Multiagent Reinforcement Learning Algorithm with Non-Linear Dynamics.” Journal of Artificial Intelligence 33 (1): 521–49. https://doi.org/10.1613/jair.2628.

Abido, Mohammed A. 2003. “Environmental/Economic Power Dispatch Using Multiobjective Evolutionary Algorithms.” In Power Engineering Society General Meeting, 920–25. Toronto, Canada: IEEE. https://doi.org/10.1109/PES.2003.1270431.

Akkermans, Hans, Jos Schreinemakers, and Koen Kok. 2004. “Emergence of Control in a Large-Scale Society of Economic Physical Agents.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 1232–34. New York, NY, USA. https://dl.acm.org/citation.cfm?id=1018900.

Albert, Réka, and Albert-László Barabási. 2002. “Statistical Mechanics of Complex Networks.” Reviews of Modern Physics 74 (1): 47–98. https://doi.org/10.1103/RevModPhys.74.47.

Al-Fuqaha, Ala, Mohsen Guizani, Mehdi Mohammadi, Mohammed Aledhari, and Moussa Ayyash. 2015. “Internet of Things: A Survey on Enabling Technologies, Protocols, and Applications.” IEEE Communications Surveys & Tutorials 17 (4): 2347–76. https://doi.org/10.1109/COMST.2015.2444095.

Apt, Krzysztof R, and Roland N Bol. 1994. “Logic Programming and Negation: A Survey.” The Journal of Logic Programming 19: 9–71. https://doi.org/10.1016/0743-1066(94)90024-8.

Arora, Anish, Prabal Dutta, Sandip Bapat, Vinod Kulathumani, Hongwei Zhang, Vinayak Naik, Vineet Mittal, et al. 2004. “A Line in the Sand: A Wireless Sensor Network for Target Detection, Classification, and Tracking.” Computer Networks 46 (5): 605–34. https://doi.org/10.1016/j.comnet.2004.06.007.

Athreya, Arjun P, Bruce DeBruhl, and Patrick Tague. 2013. “Designing for Self-Configuration and Self-Adaptation in the Internet of Things.” In International Workshop on Internet of Things, 585–92. Austin, TX, USA: ICST. https://doi.org/10.4108/icst.collaboratecom.2013.254091.

Bar-Shalom, Yaakov, and Leon Campo. 1986. “The Effect of the Common Process Noise on the Two-Sensor Fused-Track Covariance.” IEEE Transactions on Aerospace and Electronic Systems 22 (6): 803–5. https://doi.org/10.1109/TAES.1986.310815.

Ben-Ari, Mordechai. 2012. “First-Order Logic: Logic Programming.” In Mathematical Logic for Computer Science, 205–22. London, UK: Springer. https://doi.org/10.1007/978-1-4471-4129-7_11.

Bertino, Elisa, Kim-Kwang Raymond Choo, Dimitrios Georgakopolous, and Surya Nepal. 2016. “Internet of Things (IoT): Smart and Secure Service Delivery.” ACM Transactions on Internet Technology 16 (4): 22:1–7. https://doi.org/10.1145/3013520.

Binetti, Giulio, Ali Davoudi, Frank L Lewis, David Naso, and Biagio Turchiano. 2014. “Distributed Consensus-Based Economic Dispatch with Transmission Losses.” IEEE Transactions on Power Systems 29 (4): 1711–20. https://doi.org/10.1109/TPWRS.2014.2299436.

Boerkoel, James C., and Edmund H. Durfee. 2013. “Distributed Reasoning for Multiagent Simple Temporal Problems.” Journal of Artificial Intelligence 47 (1): 95–156. https://dl.acm.org/doi/10.5555/2566972.2566976.

Boutilier, Craig. 1996. “Planning, Learning and Coordination in Multiagent Decision Processes.” In Proceedings of the Conference on Theoretical Aspects of Rationality and Knowledge, 195–210. De Zeeuwse Stromen, The Netherlands. https://dl.acm.org/citation.cfm?id=1029710.

Bradbury, Jeremy S, James R Cordy, Juergen Dingel, and Michel Wermelinger. 2004. “A Survey of Self-Management in Dynamic Software Architecture Specifications.” In Proceedings of the Workshop on Self-Managed Systems, 28–33. Newport Beach, CA, USA: ACM SIGSOFT. https://doi.org/10.1145/1075405.1075411.

Cai, Niannian, Nguyen Thi Thanh Nga, and Joydeep Mitra. 2012. “Economic Dispatch in Microgrids Using Multi-Agent System.” In North American Power Symposium, 1–5. Champaign, IL, USA: IEEE. https://doi.org/10.1109/NAPS.2012.6336435.

Cao, Fuyuan, Jiye Liang, and Guang Jiang. 2009. “An Initialization Method for the K-Means Algorithm Using Neighborhood Model.” Computers & Mathematics with Applications 58 (3): 474–83. https://doi.org/10.1016/j.camwa.2009.04.017.

Carli, Ruggero, Alessandro Chiuso, Luca Schenato, and Sandro Zampieri. 2008. “Distributed Kalman Filtering Based on Consensus Strategies.” IEEE Journal on Selected Areas in Communications 26 (4): 622–33. https://doi.org/10.1109/JSAC.2008.080505.

Chechetka, Anton, and Katia Sycara. 2006. “No-Commitment Branch and Bound Search for Distributed Constraint Optimization.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 1427–29. Hakodate, Hokkaido, Japan. https://doi.org/10.1145/1160633.1160900.

Chen, Dingding, Yanchen Deng, Ziyu Chen, Wenxing Zhang, and Zhongshi He. 2020. “HS-CAI: A Hybrid DCOP Algorithm via Combining Search with Context-Based Inference.” In Proceedings of the Conference on Artificial Intelligence. New York, NY, USA: AAAI. https://arxiv.org/abs/1911.12716.

Chen, Ziyu, Yanchen Deng, and Tengfei Wu. 2017. “An Iterative Refined Max-Sum_AD Algorithm via Single-Side Value Propagation and Local Search.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 195–202. São Paulo, Brazil. https://dl.acm.org/doi/10.5555/3091125.3091158.

Chen, Ziyu, Chen He, Zhen He, and Minyou Chen. 2018. “BD-ADOPT: A Hybrid DCOP Algorithm with Best-First and Depth-First Search Strategies.” Artificial Intelligence Review 50 (2): 161–99. https://doi.org/10.1007/s10462-017-9540-z.

Choudhury, Moumita, Saaduddin Mahmudand, and Md. Mosaddek Khan. 2019. “A Particle Swarm Based Algorithm for Functional Distributed Constraint Optimization Problems.” arXiv Preprint. https://arxiv.org/pdf/1909.06168.pdf.

Clark, David. 1988. “The Design Philosophy of the DARPA Internet Protocols.” ACM SIGCOMM Computer Communication Review 18 (4): 106–14. https://doi.org/10.1145/52325.52336.

Cohen, Liel, and Roie Zivan. 2017. “Max-Sum Revisited: The Real Power of Damping.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 1505–7. São Paolo, Brazil. https://doi.org/10.1007/978-3-319-71679-4_8.

Colson, Christopher M, and M Hashem Nehrir. 2013. “Comprehensive Real-Time Microgrid Power Management and Control with Distributed Agents.” IEEE Transactions on Smart Grid 4 (1): 617–27. https://doi.org/10.1109/TSG.2012.2236368.

Dai, Haipeng, Yunhuai Liu, Guihai Chen, Xiaobing Wu, and Tian He. 2014a. “Safe Charging for Wireless Power Transfer.” In Proceedings of the International Conference on Computer Communications, 1105–13. Toronto, Canada: IEEE. https://doi.org/10.1109/INFOCOM.2014.6848041.

———. 2014b. “SCAPE: Safe Charging with Adjustable Power.” In Proceedings of the International Conference on Distributed Computing Systems, 439–48. Madrid, Spain. https://doi.org/10.1109/ICDCS.2014.52.

de Filho, Julio Oliveira, Zoltan Papp, Relja Djapic, and Job Oostveen. 2013. “Model-Based Design of Self-Adapting Networked Signal Processing Systems.” In Proceedings of the International Conference on Self-Adaptive and Self-Organizing Systems, 41–50. Philadelphia, PA, USA. https://doi.org/10.1109/SASO.2013.16.

Deng, Yanchen, Ziyu Chen, Dingding Chen, Xingqiong Jiang, and Qiang Li. 2019. “PT-ISABB: A Hybrid Tree-Based Complete Algorithm to Solve Asymmetric Distributed Constraint Optimization Problems.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 1506–14. Montreal, Canada. https://dl.acm.org/doi/10.5555/3306127.3331864.

Derler, Patricia, Edward A Lee, and Alberto Sangiovanni Vincentelli. 2012. “Modeling Cyber–Physical Systems.” Proceedings of the IEEE 100 (1): 13–28. https://doi.org/10.1109/JPROC.2011.2160929.

Di Marzo Serugendo, Giovanna, Marie-Pierre Gleizes, and Anthony Karageorgos. 2005. “Self-Organization in Multi-Agent Systems.” Knowledge Engineering Review 20 (2): 165–89. https://doi.org/10.1017/S0269888905000494.

Dolezel, Petr, Pavel Skrabanek, and Lumir Gago. 2016. “Weight Initialization Possibilities for Feedforward Neural Network with Linear Saturated Activation Functions.” In Proceedings of the Conference on Programmable Devices and Embedded Systems, 49–54. Brno, Czech Republic: IFAC. https://doi.org/10.1016/j.ifacol.2016.12.009.

Duffy, Ken R., Charles Bordenave, and Douglas J. Leith. 2013. “Decentralized Constraint Satisfaction.” IEEE/ACM Transactions on Networking 21 (4): 1298–308. https://doi.org/10.1109/TNET.2012.2222923.

Durrant-Whyte, H. F., B. Y. S. Rao, and H. Hu. 1990. “Towards a Fully Decentralized Architecture for Multi-Sensor Data Fusion.” In International Conference on Robotics and Automation, 1331–36. Cincinnati, OH, USA: IEEE. https://doi.org/10.1109/ROBOT.1990.126185.

Elidrisi, Mohamed, Nicholas Johnson, Maria Gini, and Jacob Crandall. 2014. “Fast Adaptive Learning in Repeated Stochastic Games by Game Abstraction.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 1141–48. Paris, France. https://dl.acm.org/citation.cfm?id=2617427.

Endler, M, and J Wei. 1992. “Programming Generic Dynamic Reconfigurations for Distributed Applications.” In International Workshop on Configurable Distributed Systems, 68–79. London, UK: IET. https://ieeexplore.ieee.org/abstract/document/152129.

Farinelli, Alessandro, Alex Rogers, Adrian Petcu, and Nicholas R. Jennings. 2008. “Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 639–46. Estoril, Portugal. https://dl.acm.org/citation.cfm?id=1402313.

Fatima, S Shaheen, and Michael Wooldridge. 2001. “Adaptive Task Resources Allocation in Multi-Agent Systems.” In Proceedings of the International Conference on Autonomous Agents, 537–44. Montréal, Canada. https://doi.org/10.1145/375735.376439.

Ferber, Jacques. 1999. Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc. https://dl.acm.org/citation.cfm?id=520715.

Feurer, Matthias, Jost Tobias Springenberg, and Frank Hutter. 2015. “Initializing Bayesian Hyperparameter Optimization via Meta-Learning.” In Proceedings of the Conference on Artificial Intelligence, 1128–35. Austin, TX, USA: AAAI. https://dl.acm.org/citation.cfm?id=2887007.2887164.

Fioretto, Ferdinando, Agostino Dovier, and Enrico Pontelli. 2019. “Distributed Multi-Agent Optimization for Smart Grids and Home Automation.” Intelligenza Artificiale 12 (2): 67–87. https://doi.org/10.3233/IA-180037.

Fioretto, Ferdinando, Enrico Pontelli, and William Yeoh. 2018. “Distributed Constraint Optimization Problems and Applications: A Survey.” Journal of Artificial Intelligence 61 (1). https://arxiv.org/pdf/1602.06347.pdf.

Fioretto, Ferdinando, William Yeoh, Enrico Pontelli, Ye Ma, and Satishkumar Ranade. 2017. “A Distributed Constraint Optimization (DCOP) Approach to the Economic Dispatch with Demand Response.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 999–1007. São Paulo, Brazil. https://dl.acm.org/citation.cfm?id=3091265.

Fitzpatrick, Stephen, and Lambert Meertens. 2003. “Distributed Coordination Through Anarchic Optimization.” In Distributed Sensor Networks. Multiagent Systems, Artificial Societies, and Simulated Organizations, edited by V. Lesser, C. L. Ortiz, and M. Tambe, 9:257–95. Boston, MA, USA: Springer. https://doi.org/10.1007/978-1-4615-0363-7_11.

Fransman, Jeroen, Joris Sijs, Henry Dol, Erik Theunissen, and Bart de Schutter. 2020. “Distributed Bayesian: A Continuous Distributed Constraint Optimization Problem Solver.” arXiv Preprint. https://arxiv.org/pdf/2002.03252.pdf.

Fu, Lingkun, Peng Cheng, Yu Gu, Jiming Chen, and Tian He. 2013. “Minimizing Charging Delay in Wireless Rechargeable Sensor Network.” In Proceedings of the International Conference on Computer Communications. Turin, Italy. https://doi.org/10.1109/INFCOM.2013.6567103.

Galinina, Olga, Konstantin Mikhaylov, Kaibin Huang, Sergey Andreev, and Yevgeni Koucheryavy. 2018. “Wirelessly Powered Urban Crowd Sensing over Wearables: Trading Energy for Data.” IEEE Wireless Communications 25 (2): 140–49. https://doi.org/10.1109/MWC.2018.1600468.

Gao, Hao, Marion K. Matters-Kammerer, Pieter Harpe, Dusan Milosevic, Arthur van Roermund, Jean-Paul Linnartz, and Peter G. M. Baltus. 2014. “A 60-GHz Energy Harvesting Module with on-Chip Antenna and Switch for Co-Integration with ULP Radios in 65-Nm CMOS with Fully Wireless Mm-Wave Power Transfer Measurement.” In Proceedings of the International Symposium on Circuits and Systems, 1640–43. Melbourne, Australia: IEEE. https://doi.org/10.1109/ISCAS.2014.6865466.

Gasser, Les, Carl Braganza, and Nava Herman. 1988. “Implementing Distributed AI Systems Using MACE.” In Readings in Distributed Artificial Intelligence, 445–50. Morgan Kaufmann Publishers, Inc. https://doi.org/10.1016/B978-0-934613-63-7.50047-4.

Gemine, Quentin, Damien Ernst, and Bertrand Cornélusse. 2017. “Active Network Management for Electrical Distribution Systems: Problem Formulation, Benchmark, and Approximate Solution.” Optimization and Engineering 18 (3): 587–629. https://doi.org/10.1007/s11081-016-9339-9.

Gershman, Amir, Amnon Meisels, and Roie Zivan. 2009. “Asynchronous Forward Bounding for Distributed COPs.” Journal of Artificial Intelligence 34 (1): 61–88. https://doi.org/10.1613/jair.2591.

Glinton, Robin, Katia P Sycara, and Paul Scerri. 2008. “Agent Organized Networks Redux.” In Proceedings of the Conference on Artificial Intelligence, 8:83–88. Chicago, IL, USA: AAAI. https://dl.acm.org/citation.cfm?id=1620010.

Gollakota, Shyamnath, Matthew Reynolds, Joshua Smith, and David Wetherall. 2014. “The Emergence of RF-Powered Computing.” Computer 47 (1): 32–39. https://doi.org/10.1109/MC.2013.404.

Griffiths, Nathan, and Michael Luck. 2010. “Changing Neighbours: Improving Tag-Based Cooperation.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 249–56. Toronto, Canada. https://dl.acm.org/citation.cfm?id=1838241.

Grinshpoun, Tal, Alon Grubshtein, Roie Zivan, Arnon Netzer, and Amnon Meisels. 2013. “Asymmetric Distributed Constraint Optimization Problems.” Journal of Artificial Intelligence 47 (May): 613–47. https://doi.org/10.1613/jair.3945.

Grubshtein, Alon, Roie Zivan, Tal Grinshpoun, and Amnon Meisels. 2010. “Local Search for Distributed Asymmetric Optimization.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 1015–22. Toronto, Canada. https://dl.acm.org/citation.cfm?id=1838343.

He, Shibo, Jiming Chen, Fachang Jiang, David K. Y. Yau, Guoliang Xing, and Youxian Sun. 2013. “Energy Provisioning in Wireless Rechargeable Sensor Networks.” IEEE Transactions on Mobile Computing 12 (10): 1931–42. https://doi.org/10.1109/TMC.2012.161.

Hirayama, Katsutoshi, and Makoto Yokoo. 1997. “Distributed Partial Constraint Satisfaction Problem.” In Principles and Practice of Constraint Programming, 222–36. Linz, Austria. https://doi.org/10.1007/BFb0017442.

Hoang, Khoi D., Ferdinando Fioretto, Ping Hou, Makoto Yokoo, William Yeoh, and Roie Zivan. 2016. “Proactive Dynamic Distributed Constraint Optimization.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 597–605. Singapore, Singapore. https://dl.acm.org/doi/10.5555/2936924.2937013.

Hoang, Khoi D., Ping Hou, Ferdinando Fioretto, William Yeoh, Roie Zivan, and Makoto Yokoo. 2017. “Infinite-Horizon Proactive Dynamic DCOPs.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 212–20. São Paulo, Brazil. https://dl.acm.org/doi/10.5555/3091125.3091160.

Hoang, Khoi D., William Yeoh Makoto Yokoo, and Zinovi Rabinovich. 2020. “New Algorithms for Continuous Distributed Constraint Optimization Problems.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 502–10. Auckland, New Zealand. https://dl.acm.org/doi/abs/10.5555/3398761.3398823.

Hu, Mian, Jiang-Wen Xiao, Shi-Chang Cui, and Yan-Wu Wang. 2018. “Distributed Real-Time Demand Response for Energy Management Scheduling in Smart Grid.” International Journal of Electrical Power & Energy Systems 99: 233–45. https://doi.org/10.1016/j.ijepes.2018.01.016.

Huang, Kaibin, and Vincent K. N. Lau. 2014. “Enabling Wireless Power Transfer in Cellular Networks: Architecture, Modeling and Deployment.” IEEE Wireless Communications Letters 13 (2): 902–12. https://doi.org/10.1109/TWC.2013.122313.130727.

Huang, Kaibin, and Xiangyun Zhou. 2015. “Cutting the Last Wires for Mobile Communications by Microwave Power Transfer.” IEEE Communications Magazine 53 (6): 86–93. https://doi.org/10.1109/MCOM.2015.7120022.

IEEE. 2015. “European Low Voltage Test Feeder Network (v2).” Available online: https://sites.ieee.org/pes-testfeeders/files/2017/08/European_LV_Test_Feeder_v2.zip.

Jennings, Nicholas R. 2000. “On Agent-Based Software Engineering.” Artificial Intelligence 117 (2): 277–96. https://doi.org/10.1016/S0004-3702(99)00107-1.

Johnson, David B, and David A Maltz. 1996. “Dynamic Source Routing in Ad Hoc Wireless Networks.” In Mobile Computing, edited by T. Imilienski and H. F. Korth, 153–81. Boston, MA, USA: Springer. https://doi.org/10.1007/978-0-585-29603-6_5.

Jordehi, A Rezaee. 2019. “Optimisation of Demand Response in Electric Power Systems, a Review.” Renewable and Sustainable Energy Reviews 103: 308–19. https://doi.org/10.1016/j.rser.2018.12.054.

Julier, S. J., and J. K. Uhlmann. 1997. “A Non-Divergent Estimation Algorithm in the Presence of Uknown Correlations.” In Proceedings of the American Control Conference, 2369–73. Albuquerque, NM, USA: IEEE. https://doi.org/10.1109/ACC.1997.609105.

Kalialakis, Christos, and Apostolos Georgiadis. 2014. “The Regulatory Framework for Wireless Power Transfer Systems.” Wireless Power Transfer 1 (2): 108–18. https://doi.org/10.1017/wpt.2014.13.

Karsai, Gabor, Fabio Massacci, Leon J. Osterweil, and Ina Schieferdecker. 2010. “Evolving Embedded Systems.” Computer 43 (5): 34–40. https://doi.org/10.1109/MC.2010.135.

Karsai, Gabor, and Janos Sztipanovits. 1999. “A Model-Based Approach to Self-Adaptive Software.” IEEE Intelligent Systems and Their Applications 14 (3): 4–53. https://doi.org/10.1109/5254.769884.

Kash, Ian, Ariel D Procaccia, and Nisarg Shah. 2014. “No Agent Left Behind: Dynamic Fair Division of Multiple Resources.” Journal of Artificial Intelligence 51 (1): 579–603. https://dl.acm.org/citation.cfm?id=2750439.

Kephart, Jeffrey O., and David M. Chess. 2003. “The Vision of Autonomic Computing.” Computer 36 (1): 41–50. https://doi.org/10.1109/MC.2003.1160055.

Kiekintveld, Christopher, Zhengyu Yin, Atul Kumar, and Milind Tambe. 2010. “Asynchronous Algorithms for Approximate Distributed Constraint Optimization with Quality Bounds.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 133–40. Toronto, Canada. https://dl.acm.org/doi/abs/10.5555/1838206.1838225.

Kim, Hongseok, Young-Jin Kim, Kai Yang, and Marina Thottan. 2011. “Cloud-Based Demand Response for Smart Grid: Architecture and Distributed Algorithms.” In International Conference on Smart Grid Communications, 398–403. Brussels, Belgium: IEEE. https://doi.org/10.1109/SmartGridComm.2011.6102355.

Kirti, Shrut, and Anna Scaglione. 2008. “Scalable Distributed Kalman Filtering Through Consensus.” In Proceedings of the International Conference on Acoustics, Speech and Signal Processing, 2725–28. Las Vegas, NV, USA: IEEE. https://doi.org/10.1109/ICASSP.2008.4518212.

Klauw, Thijs van der, Marco E. T. Gerards, Gerwin Hoogsteen, Gerard J. M. Smit, and Johann L. Hurink. 2016. “Considering Grid Limitations in Profile Steering.” In International Energy Conference, 1–6. Leuven, Belgium: IEEE. https://doi.org/10.1109/ENERGYCON.2016.7514033.

Kok, Koen, and Arun Subramanian. 2019. “Fast Locational Marginal Pricing for Congestion Management in a Distribution Network with Multiple Aggregators.” In International Conference and Exhibition on Electricity Distribution. Madrid, Spain. https://www.cired-repository.org/handle/20.500.12455/528.

Kok, Koen, and Steve Widergren. 2016. “A Society of Devices: Integrating Intelligent Distributed Resources with Transactive Energy.” IEEE Power and Energy Magazine 14 (3): 34–45. https://doi.org/10.1109/MPE.2016.2524962.

Kota, Ramachandra, Nicholas Gibbins, and Nicholas R Jennings. 2012. “Decentralized Approaches for Self-Adaptation in Agent Organizations.” Transactions on Autonomous and Adaptive Systems 7 (1): 1–36. https://doi.org/10.1145/2168260.2168261.

Kraus, Sarit, and Daniel Lehmann. 1995. “Designing and Building a Negotiating Automated Agent.” Computational Intelligence 11 (1): 132–71. https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8640.1995.tb00026.x.

Krikidis, Ioannis. 2014. “Simultaneous Information and Energy Transfer in Large-Scale Networks with/Without Relaying.” IEEE Transactions on Communications 62 (3): 900–912. https://doi.org/10.1109/TCOMM.2014.020914.130825.

Kumar, Akshat, Adrian Petcu, and Boi Faltings. 2008. “H-DPOP: Using Hard Constraints for Search Space Pruning in DCOP.” In Proceedings of the Conference on Artificial Intelligence, 325–30. Chicago, IL, USA: AAAI. https://dl.acm.org/doi/10.5555/1619995.1620048.

Lass, Robert N, Evan Sultanik, and William C Regli. 2008. “Dynamic Distributed Constraint Reasoning.” In Proceedings of the Conference on Artificial Intelligence, 1466–69. Chicago, IL, USA: AAAI. https://www.aaai.org/Papers/AAAI/2008/AAAI08-238.pdf.

Leeuwen, Cornelis Jan van, Vicente Hernández Díaz, Roshan Kotian, Raúl del Toro Matamoros, Zoltan Papp, and Yolanda Rieter-Barrell. 2016. “An Illustrative Application Example: Cargo State Monitoring.” In Runtime Reconfiguration in Networked Embedded Systems, edited by Zoltan Papp and George Exarchakos, 137–68. Springer Singapore. https://doi.org/10.1007/978-981-10-0715-6_6.

Leeuwen, Cornelis Jan van, and Przemysław Pawełczak. 2017. “CoCoA: A Non-Iterative Approach to a Local Search (A)DCOP Solver.” In Proceedings of the Conference on Artificial Intelligence. San Fransisco, CA, USA: AAAI. https://dl.acm.org/citation.cfm?id=3298141.

Leeuwen, Cornelis Jan van, Yolanda Rieter-Barrell, Zoltan Papp, Andrei Pruteanu, and Teus Vogel. 2016. “Model-Based Engineering of Runtime Reconfigurable Networked Embedded Systems.” In Runtime Reconfiguration in Networked Embedded Systems, edited by Zoltan Papp and George Exarchakos, 1–28. Springer Singapore. https://doi.org/10.1007/978-981-10-0715-6_1.

Leeuwen, Cornelis Jan van, Kasım Sinan Yıldırım, and Przemysław Pawełczak. 2017. “Self Adaptive Safe Provisioning of Wireless Power Using DCOPs.” In Proceedings of the International Conference on Self-Adaptive and Self-Organizing Systems. Tucson, AZ, USA. https://doi.org/10.1109/SASO.2017.16.

Lezama, Fernando, Enrique Munoz de Cote, Alessandro Farinelli, João Soares, Tiago Pinto, and Zita Vale. 2019. “Distributed Constrained Optimization Towards Effective Agent-Based Microgrid Energy Resource Management.” In Conference on Artificial Intelligence, 438–49. Villa Real, Portugal: EPIA. https://doi.org/10.1007/978-3-030-30241-2_37.

Léauté, Thomas, and Boi Faltings. 2013. “Protecting Privacy Through Distributed Computation in Multi-Agent Decision Making.” Journal of Artificial Intelligence 47: 649–95. https://doi.org/10.1613/jair.3983.

Li, Na, Lijun Chen, and Steven H. Low. 2011. “Optimal Demand Response Based on Utility Maximization in Power Networks.” In Power Engineering Society General Meeting, 1–8. Detroit, MI, USA: IEEE. https://doi.org/10.1109/PES.2011.6039082.

Liu, Qingzhi, Michał Golinński, Przemysław Pawełczak, and Martijn Warnier. 2016. “Green Wireless Power Transfer Networks.” IEEE Journal on Selected Areas in Communications 34 (5): 1740–56. https://doi.org/10.1109/JSAC.2016.2520178.

Liu, Qingzhi, Kasım Sinan Yıldırım, Przemysław Pawełczak, and Martijn Warnier. 2016. “Safe and Secure Wireless Power Transfer Networks: Challenges and Opportunities in RF-Based Systems.” IEEE Communications Magazine 54 (9): 74–79. https://doi.org/10.1109/MCOM.2016.7565191.

Liu, Weirong, Peng Zhuang, Hao Liang, Jun Peng, and Zhiwu Huang. 2018. “Distributed Economic Dispatch in Microgrids Based on Cooperative Reinforcement Learning.” IEEE Transactions on Neural Networks and Learning Systems 29 (6): 2192–2203. https://doi.org/10.1109/TNNLS.2018.2801880.

Lützenberger, Marco, Tobias Küster, Nils Masuch, and Johannes Fähndrich. 2016. “Multi-Agent System in Practice: When Research Meets Reality.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 796–805. Singapore, Singapore. https://dl.acm.org/doi/10.5555/2936924.2937041.

Maheswaran, Rajiv T., Jonathan P. Pearce, and Milind Tambe. 2004. “Distributed Algorithms for DCOP: A Graphical-Game-Based Approach.” In Proceedings of the International Conference on Parallel and Distributed Computing Systems, 432–39. San Fransisco, CA, USA: ISCA. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7011.

Maheswaran, Rajiv T., Milind Tambe, Emma Bowring, Jonathan P. Pearce, and Pradeep Varakantham. 2004. “Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 310–17. New York, NY, USA. https://dx.doi.org/10.1109/AAMAS.2004.10067.

Mahmud, Saaduddin, Moumita Choudhury, Md Khan, Long Tran-Thanh, Nicholas R Jennings, and others. 2019. “AED: An Anytime Evolutionary DCOP Algorithm.” arXiv Preprint. https://arxiv.org/pdf/1909.06254.pdf.

Mataric, Maja J. 1993. “Designing Emergent Behaviors: From Local Interactions to Collective Intelligence.” In Proceedings of the International Conference on Simulation of Adaptive Behavior, 432–41. Honolulu, HI, USA. https://doi.org/10.1007/978-3-642-79629-6_11.

Meisels, Amnon, Eliezer Kaplansky, Igor Razgon, and Roie Zivan. 2002. “Comparing Performance of Distributed Constraints Processing Algorithms.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 86–93. Bologna, Italy. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.8606.

Minton, Steven, Mark D Johnston, Andrew B Philips, and Philip Laird. 1992. “Minimizing Conflicts: A Heuristic Repair Method for Constraint Satisfaction and Scheduling Problems.” Artificial Intelligence 58 (1-3): 161–205. https://doi.org/10.1016/0004-3702(92)90007-K.

Mishra, Deepak, Swades De, Soumya Jana, Stefano Basagni, Kaushik Chowdhury, and Wendi Heinzelman. 2015. “Smart RF Energy Harvesting Communications: Challenges and Opportunities.” IEEE Communications Magazine 53 (4): 70–78. https://doi.org/10.1109/MCOM.2015.7081078.

Modi, Pragnesh Jay. 2003. “Distributed Constraint Optimization for Multiagent Systems.” PhD thesis, Los Angeles, CA, USA: University of Southern California. https://dl.acm.org/doi/book/10.5555/1037507.

Modi, Pragnesh Jay, Wei-Min Shen, Milind Tambe, and Makoto Yokoo. 2005. “ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees.” Artificial Intelligence 161 (1–2): 149–80. https://doi.org/10.1016/j.artint.2004.09.003.

Naderi, M Yousof, Prusayon Nintanavongsa, and Kaushik R Chowdhury. 2014. “RF-MAC: A Medium Access Control Protocol for Re-Chargeable Sensor Networks Powered by Wireless Energy Harvesting.” IEEE Wireless Communications Letters 13 (7): 3926–37. https://doi.org/10.1109/TWC.2014.2315211.

Nguyen, Duc Thien, William Yeoh, Hoong Chuin Lau, Shlomo Zilberstein, and Chongjie Zhang. 2014. “Decentralized Multi-Agent Reinforcement Learning in Average-Reward Dynamic DCOPs.” In Proceedings of the Conference on Artificial Intelligence. Québec, Canada: AAAI. https://dl.acm.org/doi/10.5555/2615731.2617463.

Non-Ionizing Radiation Protection (ICNIRP), International Commission on. 1998. “Guidelines for Limiting Exposure to Time-Varying Electric, Magnetic, and Electromagnetic Fields (up to 300 GHz).” Health Physics 74 (4): 494–522. https://www.icnirp.org/cms/upload/publications/ICNIRPemfgdl.pdf.

Nordstrom, Greg, Janos Sztipanovits, and Gabor Karsai. 1998. “Metalevel Extension of the MultiGraph Architecture.” In Proceedings of the Engineering of Computer Based Systems Conference, 61–68. Jerusalem, Israel: IEEE. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.5045.

Okamoto, Steven, Roie Zivan, and Aviv Nahon. 2016. “Distributed Breakout: Beyond Satisfaction.” In Proceedings of the International Joint Conference on Artificial Intelligence, 447–53. New York, NY, USA. https://dl.acm.org/citation.cfm?id=3060684.

Parhizi, Sina, Hossein Lotfi, Amin Khodaei, and Shay Bahramirad. 2015. “State of the Art in Research on Microgrids: A Review.” IEEE Access 3: 890–925. https://doi.org/10.1109/ACCESS.2015.2443119.

Pearce, Jonathan P., and Milind Tambe. 2007. “Quality Guarantees on k-Optimal Solutions for Distributed Constraint Optimization Problems.” In Proceedings of the International Joint Conference on Artificial Intelligence, 1446–51. Hyderabad, India. https://dl.acm.org/doi/10.5555/1625275.1625509.

Petcu, Adrian, and Boi Faltings. 2005a. “A Scalable Method for Multiagent Constraint Optimization.” In Proceedings of the International Joint Conference on Artificial Intelligence, 266–71. Edinburgh, Scotland, UK. https://dl.acm.org/citation.cfm?id=1642336.

———. 2005b. “Superstabilizing, Fault-Containing Distributed Combinatorial Optimization.” In Proceedings of the Conference on Artificial Intelligence, 449–54. Pittsburgh, PA, USA. https://dl.acm.org/doi/abs/10.5555/1619332.1619405.

———. 2007. “Optimal Solution Stability in Dynamic, Distributed Constraint Optimization.” In Proceedings of the International Conference on Intelligent Agent Technology, 321–27. Fremont, CA, USA: IEEE/WIC/ACM. https://doi.org/10.1109/IAT.2007.11.

Pipattanasomporn, Manisa, Hassan Feroze, and Saifur Rahman. 2009. “Multi-Agent Systems in a Distributed Smart Grid: Design and Implementation.” In Power Systems Conference and Exposition, 1–8. Seattle, WA, USA: IEEE. https://doi.org/10.1109/PSCE.2009.4840087.

Rahnamayan, Shahryar, Hamid R. Tizhoosh, and Magdy M. A. Salama. 2007. “A Novel Population Initialization Method for Accelerating Evolutionary Algorithms.” Computers & Mathematics with Applications 53 (10): 1605–14. https://doi.org/10.1016/j.camwa.2006.07.013.

Rassa, Abo, Coen van Leeuwen, Robertjan Spaans, and Koen Kok. 2019. “Developing Local Energy Markets: A Holistic System Approach.” IEEE Power and Energy Magazine 17 (5): 59–70. https://doi.org/10.1109/MPE.2019.2921743.

Ribeiro, Alejandro, Ioannis D. Schizas, Stergios I. Roumeliotis, and Georgios B. Giannakis. 2010. “Kalman Filtering in Wireless Sensor Networks: Reducing Communication Cost in State-Estimation Problems.” IEEE Control Systems Magazine 30 (2): 66–86. https://doi.org/10.1109/MCS.2009.935569.

Rogers, Alex, Alessandro Farinelli, Ruben Stranders, and Nicholas R. Jennings. 2011. “Bounded Approximate Decentralised Coordination via the Max-Sum Algorithm.” Artificial Intelligence 175 (2): 730–59. https://dx.doi.org/10.1016/j.artint.2010.11.001.

Ross, Dale W, and Sungkook Kim. 1980. “Dynamic Economic Dispatch of Generation.” IEEE Transactions on Power Apparatus and Systems PAS-99 (6): 2060–68. https://doi.org/10.1109/TPAS.1980.319847.

Rossi, Gianfranco. 1986. “Uses of Prolog in Implementation of Expert Systems.” New Generation Computing 4 (3): 321–29. https://doi.org/10.1007/BF03037410.

Sarker, Amit, Abdullahil Baki Arif, Moumita Choudhury, and Md. Mosaddek Khan. 2020. “C-CoCoA: A Continuous Cooperative Constraint Approximation Algorithm to Solve Functional DCOPs.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 1990–92. Auckland, New Zealand. https://dl.acm.org/doi/abs/10.5555/3398761.3399051.

Sculley, David, Gary Holt, Daniel Golovin, Eugene Davydov, Todd Phillips, Dietmar Ebner, Vinay Chaudhary, Michael Young, Jean-Francois Crespo, and Dan Dennison. 2015. “Hidden Technical Debt in Machine Learning Systems.” In Advances in Neural Information Processing Systems, 2503–11. Montréal, Canada. https://papers.nips.cc/paper/5656-hidden-technical-debt-in-machine-learning-systems.

Shaikh, Faisal Karim, Sherali Zeadally, and Ernesto Exposito. 2015. “Enabling Technologies for Green Internet of Things.” IEEE Systems Journal 11 (2): 983–94. https://doi.org/10.1109/JSYST.2015.2415194.

Sijs, Joris. 2012. “State Estimation in Networked Systems.” PhD thesis, Eindhoven, the Netherlands: Eindhoven University of Technology. https://doi.org/10.6100/IR730947.

Sijs, Joris, and Mircea Lazar. 2011. “A Distributed Kalman Filter with Global Covariance.” In Proceedings of the American Control Conference, 4840–45. San Francisco, USA: IEEE. https://doi.org/10.1109/ACC.2011.5990802.

———. 2012. “State Fusion with Unknown Correlation: Ellipsoidal Intersection.” Automatica 48 (8): 1874–78. https://doi.org/10.1016/j.automatica.2012.05.077.

Sijs, Joris, and Zoltan Papp. 2012. “Towards Self-Organizing Kalman Filters.” In Proceedings of the International Conference on Information Fusion, 1012–19. Singapore, Singapore: IEEE. https://ieeexplore.ieee.org/abstract/document/6289913.

Simonot, Marianne, and Virginia Aponte. 2009. “A Declarative Formal Approach to Dynamic Reconfiguration.” In Proceedings of the International Workshop on Open Component Ecosystems, 1–10. Amsterdam, the Netherlands. https://doi.org/10.1145/1595800.1595802.

Smith, Joshua R. 2013. Wirelessly Powered Sensor Networks and Computational RFID. New York, NY, USA: Springer. https://doi.org/10.1007/978-1-4419-6166-2.

Stärk, Robert. 1989. “A Direct Proof for the Completeness of SLD-Resolution.” In International Workshop on Computer Science Logic, 382–83. Kaiserslautern, Germany. https://doi.org/10.1007/3-540-52753-2_52.

Stranders, Ruben, Long Tran-Thanh, Francesco M Delle Fave, Alex Rogers, and Nicholas R Jennings. 2012. “DCOPs and Bandits: Exploration and Exploitation in Decentralised Coordination.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 289–96. Valencia, Spain. https://dl.acm.org/doi/10.5555/2343576.2343617.

Tahbaz-Salehi, Alireza, and Ali Jadbabaie. 2010. “Consensus over Ergodic Stationary Graph Processes.” IEEE Transactions on Automatic Control 55 (1): 225–30. https://doi.org/10.1109/TAC.2009.2034054.

Tassa, Tamir, Tal Grinshpoun, and Roie Zivan. 2017. “Privacy Preserving Implementation of the Max-Sum Algorithm and Its Variants.” Journal of Artificial Intelligence 59: 311–49. https://doi.org/10.1613/jair.5504.

Vardakas, John S, Nizar Zorba, and Christos V Verikoukis. 2014. “A Survey on Demand Response Programs in Smart Grids: Pricing Methods and Optimization Algorithms.” IEEE Communications Surveys and Tutorials 17 (1): 152–78. https://doi.org/10.1109/COMST.2014.2341586.

Velasquez, Miguel A., Julian Barreiro-Gomez, Nicanor Quijano, Angela I. Cadena, and Mohammad Shahidehpour. 2019. “Distributed Model Predictive Control for Economic Dispatch of Power Systems with High Penetration of Renewable Energy Resources.” International Journal of Electrical Power & Energy Systems 113: 607–17. https://doi.org/10.1016/j.ijepes.2019.05.044.

Visser, Hubregt J., and Ruud J. M. Vullers. 2013. “RF Energy Harvesting and Transport for Wireless Sensor Network Applications: Principles and Requirements.” Proceedings of the IEEE 101 (6): 1410–23. https://doi.org/10.1109/JPROC.2013.2250891.

Warrington, Joseph, Sébastien Mariéthoz, and Manfred Morari. 2011. “Negotiated Predictive Dispatch: Receding Horizon Nodal Electricity Pricing for Wind Integration.” In International Conference on the European Energy Market, 407–12. Zagreb, Croatia: IEEE. https://doi.org/10.1109/EEM.2011.5953046.

Wu, Ting, Theodore S. Rappaport, and Christopher M. Collins. 2015. “Safe for Generations to Come: Considerations of Safety for Millimeter Waves in Wireless Communications.” IEEE Microwave Magazine 16 (2): 65–84. https://doi.org/10.1109/MMM.2014.2377587.

Xiao, Lin, and Stephen Boyd. 2004. “Fast Linear Iterations for Distributed Averaging.” Systems and Control Letters 53 (1): 65–78. https://doi.org/10.1016/j.sysconle.2004.02.022.

Xu, Li Da, Wu He, and Shancang Li. 2014. “Internet of Things in Industries: A Survey.” IEEE Transactions on Industrial Informatics 10 (4): 2233–43. https://doi.org/10.1109/TII.2014.2300753.

Yam, Jim Y. F., and Tommy W. S. Chow. 2000. “A Weight Initialization Method for Improving Training Speed in Feedforward Neural Network.” Neurocomputing 30 (1): 219–32. https://doi.org/10.1016/S0925-2312(99)00127-7.

Ye, Dayong, Minjie Zhang, and Athanasios V Vasilakos. 2016. “A Survey of Self-Organization Mechanisms in Multiagent Systems.” IEEE Transactions on Systems, Man, and Cybernetics: Systems 47 (3): 441–61. https://doi.org/10.1109/TSMC.2015.2504350.

Yedidsion, Harel, Roie Zivan, and Alessandro Farinelli. 2014. “Explorative Max-Sum for Teams of Mobile Sensing Agents.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 549–56. Paris, France. https://dl.acm.org/doi/10.5555/2615731.2615821.

Yeoh, William, Pradeep Varakantham, Xiaoxun Sun, and Sven Koenig. 2015. “Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems.” In Proceedings of the International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2:257–64. Singapore, Singapore: IEEE/WIC/ACM. https://doi.org/10.1109/WI-IAT.2015.114.

Yeoh, William, and Makoto Yokoo. 2012. “Distributed Problem Solving.” AI Magazine 33 (3): 53–65. https://doi.org/10.1609/aimag.v33i3.2429.

Ygge, Fredrik, and Hans Akkermans. 1999. “Decentralized Markets Versus Central Control: A Comparative Study.” Journal of Artificial Intelligence 11 (1): 301–33. https://arxiv.org/ct?url=https.

Yokoo, Makoto, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara. 1998. “The Distributed Constraint Satisfaction Problem: Formalization and Algorithms.” IEEE Transactions on Knowledge and Data Engineering 10 (5): 673–85. https://doi.org/10.1109/69.729707.

Zhang, Chongjie, Victor Lesser, and Prashant Shenoy. 2009. “A Multi-Agent Learning Approach to Online Distributed Resource Allocation.” In Proceedings of the International Joint Conference on Artificial Intelligence, 361–66. Pasadena, CA, USA. https://dl.acm.org/citation.cfm?id=1661503.

Zhang, Honghai, and Jennifer C Hou. 2005. “Maintaining Sensing Coverage and Connectivity in Large Sensor Networks.” Ad Hoc & Sensor Wireless Networks 1: 89–124. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.1155.

Zhang, Weixiong, Guandong Wang, Xing Zhao, and Lars Wittenburg. 2005. “Distributed Stochastic Search and Distributed Breakout: Properties, Comparison and Applications to Constraint Optimization Problems in Sensor Networks.” Artificial Intelligence 161 (1): 55–87. https://doi.org/10.1016/j.artint.2004.10.004.

Zivan, Roie, Robin Glinton, and Katia Sycara. 2009. “Distributed Constraint Optimization for Large Teams of Mobile Sensing Agents.” In Proceedings of the International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2:347–54. Milan, Italy: IEEE/WIC/ACM. https://doi.org/10.1109/WI-IAT.2009.176.

Zivan, Roie, Steven Okamoto, and Hilla Peled. 2014. “Explorative Anytime Local Search for Distributed Constraint Optimization.” Artificial Intelligence 212 (July): 1–26. https://doi.org/10.1016/j.artint.2014.03.002.

Zivan, Roie, Tomer Parash, and Yarden Naveh. 2015. “Applying Max-Sum to Asymmetric Distributed Constraint Optimization.” In Proceedings of the International Joint Conference on Artificial Intelligence, 432–38. Buenos Aires, Argentina. https://dl.acm.org/citation.cfm?id=2832249.2832309.

Zivan, Roie, and Hilla Peled. 2012. “Max/Min-Sum Distributed Constraint Optimization Through Value Propagation on an Alternating DAG.” In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 265–72. Valencia, Spain. https://dl.acm.org/doi/10.5555/2343576.2343614.